Table of contents
1.
Introduction
2.
What is a scrambled string?
3.
Problem Statement
3.1.
Example
4.
Recursion 
4.1.
Primary Condition
4.2.
Algorithm
4.3.
Implementation
4.4.
C++
4.5.
Java
4.6.
Python
4.7.
C#
4.8.
JavaScript
4.8.1.
Input
4.8.2.
Output
4.9.
Time Complexity
4.10.
Space Complexity
5.
Dynamic Programming
5.1.
Algorithm
5.2.
Implementation
5.3.
C++
5.4.
Java
5.5.
Python
5.6.
JavaScript
5.7.
C#
5.7.1.
Input
5.7.2.
Output
5.8.
Time Complexity
5.9.
Space Complexity
6.
Frequently Asked Questions
6.1.
What is the time complexity of scrambled string?
6.2.
How do you jumble strings in Python?
7.
Conclusion
Last Updated: Sep 6, 2024
Medium

Scramble String

Author Ishita Chawla
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

There are several problems that cannot be solved using regular algorithms like greedy or divide and conquer, or the solutions they provide are not optimal.

So, we use Dynamic Programming, which is an optimisation of simple recursion to solve such problems. The basic idea is to store the results of sub-problems to avoid recalculation and reduce the time complexity of the problems.

Scramble String

This blog will discuss one such problem, Scramble String, which can easily be solved using recursion. This is not the optimised approach as it might give the error of time limit exceeding in case of more significant constraints because of which this method is not suitable. It consumes ample time and space as it makes repetitive calls and uses a stack in the memory. So, we optimise the time and space complexity, and to check whether the string is a scrambled string or not, we will use dynamic programming.

What is a scrambled string?

A Scrambled string is a string which is obtained after swapping the sibling nodes in the binary representation of a string. We can represent a string in the form of a binary tree by recursively dividing it into two non-empty substrings. To scramble the string, we just have to swap the 2 children of a non-leaf node. 

example

For e.g. We can convert node “ni” and swap its two children. It produces a scrambled string “innja”.

example scramble string

We basically split the string into non-empty substrings by choosing a random index of a string S and dividing it into 2 halves, say A and B.

So if we use A and B to reconstruct our original string S, there are 2 possibilities:

  • S = A + B  (Order remains same.)
  • S = B + A  (Order has been reversed.)

 

Also Read About, Byte Array to String

Problem Statement

You are given strings S1 and S2, and the task is to determine whether S2 is a scrambled form of string S1 or not.

Example

 

  1.      S1 = “ACTIVE“

S2 = “EVITAC”

In this case, string S2 is the scrambled form of string S1.

What is a scrambled string

In this example, we see that we can divide the word “ACTIVE” into 2 halves of length 2 and 3 and these 2 halves can also be divided into 2 halves and so on and it forms a recursive tree and in the end, we are left with leaf nodes which cannot be divided further as they have only 1 character left in them.

So now we start merging the leaf nodes in an arbitrary order to form the parent node. Now, this parent node can also merge with his sibling in any order. We can get multiple permutations of the original string using this algorithm.

 2.      S1 = “ACTOR“

S2 = “RCATO”

scrambled string example"

 

In this case, string S2 is not a scrambled form of S1 asand being adjacent is not possible.

Having understood the problem, move ahead to Coding Ninjas Studio and first try solving the problem on your own.

Now, let us solve this problem using basic recursion, and then we will optimize our solution with the help of dynamic programming. 

Recursion 

Before we proceed with the algorithm, we need to keep in mind the following observations:

  • In the case of single characters, they have to be equal; else the strings will not be scrambled.

For example,

S1 = “A“

S2 = “A”

So, S1 and S2 are scrambled strings, but if we look at the case of:

S1 = “Z“

S2 = “A”

The strings are not scrambled. 

 

  • Now, if the length of the string is equal to N, the total number of partition points is equal to N - 1. For example,
example

Thus, for N = 5, the number of partitioning points = 4.          

  • Similarly, there will be N - 1 possible trees.
  • We need to try partitioning at all possible points, and check whether there exists a combination in S1 that results in string S2.
  • Since the string is divided into parts at every step, the recursion tree will be a binary tree structure. 

Primary Condition

Since we are given strings, S1 and S2, of equal length N, we have to find an index such that at least one of the following holds:

  1. S2[0. . .i - 1] is a scrambled string of S1[0. . .i-1] and S2[i . . .N - 1] is a scrambled string of S1[i . . .N - 1]. 

In other words, the first characters of S2 should be equal to the firstcharacters of S1, and the last N - i  characters of S2 should be equal to the last N - i characters of S1.

 2. S2[N - i. . . N - 1] is a scrambled string of S1[0. . .i - 1] and S2[0. . . i - 1] is a scrambled string of S1[N - i . . .N - 1]. 

In other words, the last N - i characters of S2 should be equal to the first i characters of S1 and the firstcharacters of S2 should be equal to the last N - i characters of S1.

Sounds confusing? 

Well, let us try and understand this more thoroughly.

Let the strings S1 and S2 be

S1 = “ABCDEF“

S2 = “BCDAEF”

Algorithm

  • Create a recursive function that will check if the given strings are scrambled or not.
  • If the strings are equal, the function will always return true.
  • If not, we will try all possible combinations of partitioning the string.
  • If the above condition meets, the function will return true, else it will return false.

Implementation

  • C++
  • Java
  • Python
  • C#
  • JavaScript

C++

/* C++ program to check if two given strings are scrambled or not using recursion. */
#include <iostream>
#include <string>
using namespace std;

// Recursive function to check if the strings are scrambled.
bool solveScramble(string s1, string s2)
{
// If the size of the string is 1, then S1 and S2 should contain the same character.
if (s1.size() == 1)
return s1 == s2;


// If the strings are equal, they will definitely be scrambled strings.
if (s1 == s2)
return true;

int n = s1.size();
bool res = false;

// Loop to check all possible combinations of the strings that can be formed.
for (int i = 1; i < n; ++i)
{
// First check if S2[0..i-1] is a scrambled string of S1[0..i-1] and S2[i..n-1] is a scrambled string of S1[i..n-1].
// If not, check if S2[n-i..n-1] is a scrambled string of S1[0..i-1] and S2[0..i-1] is a scrambled string of S1[n-i..n-1].
// If any of the above conditions hold, the function will return true.

if ((solveScramble(s1.substr(0, i), s2.substr(0, i)) && solveScramble(s1.substr(i), s2.substr(i))) || (solveScramble(s1.substr(0, i), s2.substr(n - i)) && solveScramble(s1.substr(i), s2.substr(0, n - i))))
return true;
}

// In case none of the above conditions is satisfied, the function will return false by default.
return false;
}

int main()
{
string s1, s2;

// Taking user input.
cout << "Enter the two strings\n";
cin >> s1 >> s2;

// Calling the function to check the strings.
if (solveScramble(s1, s2))
cout << "Yes the string " << s2 << " is a scramble string of " << s1;
else
cout << "No, the string " << s2 << " is not a scramble string of " << s1;

return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Java

import java.util.Scanner;

public class ScrambleString {

public static boolean solveScramble(String s1, String s2) {
if (s1.length() == 1)
return s1.equals(s2);

if (s1.equals(s2))
return true;

int n = s1.length();

for (int i = 1; i < n; i++) {
if ((solveScramble(s1.substring(0, i), s2.substring(0, i)) && solveScramble(s1.substring(i), s2.substring(i))) ||
(solveScramble(s1.substring(0, i), s2.substring(n - i)) && solveScramble(s1.substring(i), s2.substring(0, n - i))))
return true;
}
return false;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the two strings:");
String s1 = sc.next();
String s2 = sc.next();

if (solveScramble(s1, s2))
System.out.println("Yes, the string " + s2 + " is a scramble string of " + s1);
else
System.out.println("No, the string " + s2 + " is not a scramble string of " + s1);
}
}
You can also try this code with Online Java Compiler
Run Code

Python

def solve_scramble(s1, s2):
if len(s1) == 1:
return s1 == s2

if s1 == s2:
return True

n = len(s1)

for i in range(1, n):
if (solve_scramble(s1[:i], s2[:i]) and solve_scramble(s1[i:], s2[i:])) or \
(solve_scramble(s1[:i], s2[-i:]) and solve_scramble(s1[i:], s2[:-i])):
return True
return False


if __name__ == "__main__":
s1 = input("Enter the first string: ")
s2 = input("Enter the second string: ")

if solve_scramble(s1, s2):
print(f"Yes, the string {s2} is a scramble string of {s1}")
else:
print(f"No, the string {s2} is not a scramble string of {s1}")
You can also try this code with Online Python Compiler
Run Code

C#

using System;

class ScrambleString
{
static bool SolveScramble(string s1, string s2)
{
if (s1.Length == 1)
return s1 == s2;

if (s1 == s2)
return true;

int n = s1.Length;
bool res = false;

for (int i = 1; i < n; i++)
{
if ((SolveScramble(s1.Substring(0, i), s2.Substring(0, i)) && SolveScramble(s1.Substring(i), s2.Substring(i))) ||
(SolveScramble(s1.Substring(0, i), s2.Substring(n - i)) && SolveScramble(s1.Substring(i), s2.Substring(0, n - i))))
return true;
}

return false;
}

static void Main()
{
Console.WriteLine("Enter the two strings:");
string s1 = Console.ReadLine();
string s2 = Console.ReadLine();

if (SolveScramble(s1, s2))
Console.WriteLine($"Yes, the string {s2} is a scramble string of {s1}");
else
Console.WriteLine($"No, the string {s2} is not a scramble string of {s1}");
}
}

JavaScript

function solveScramble(s1, s2) {
if (s1.length === 1) return s1 === s2;

if (s1 === s2) return true;

let n = s1.length;

for (let i = 1; i < n; i++) {
if ((solveScramble(s1.substring(0, i), s2.substring(0, i)) && solveScramble(s1.substring(i), s2.substring(i))) ||
(solveScramble(s1.substring(0, i), s2.substring(n - i)) && solveScramble(s1.substring(i), s2.substring(0, n - i))))
return true;
}
return false;
}

const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});

readline.question('Enter the two strings:\n', (input) => {
const [s1, s2] = input.split(" ");
if (solveScramble(s1, s2))
console.log(`Yes, the string ${s2} is a scramble string of ${s1}`);
else
console.log(`No, the string ${s2} is not a scramble string of ${s1}`);
readline.close();
});
You can also try this code with Online Javascript Compiler
Run Code

 

Input

Enter the two strings:
active
evitac


Output

Yes, the string evitac is a scramble string of active.

Time Complexity

The time complexity of this technique is given by O(2N) where is the length of either of the 2 strings.

The function uses recursion, and in the worst case, it has to try all possible combinations. Thus, the time complexity of this technique is exponential and is given by  O(2N).

Space Complexity

The space complexity is given by O(N) where is the length of either of the 2 strings.

Since recursion uses a call stack, there will be N  calls to the function, and hence the space complexity is given by O(N). 

Read More - Time Complexity of Sorting Algorithms

Dynamic Programming

Though the logic for the above approach is correct, the main problem is that of recalculations, which wastes a lot of time and space. So, an optimal approach to solve this problem is by using dynamic programming.

In this technique, we will be using a hashmap or a memoization array to store the results of the sub-problems. The rest of the logic, though, will remain the same.

Algorithm

  1. Create a recursive function that will check if the given strings are scrambled or not.
  2. We will maintain a 2-D memoization array or a simple unordered hash map of type <string, bool>, i.e., the value will either be true or false, where we will store the boolean values of substrings in an unordered map. So, if the value has occurred previously, we can get the value easily from the map, rather than calling the recursive function again.
  3. If the strings are equal, the function will always return true.
  4. If not, we will try all possible combinations of partitioning the string by calling the function and storing the values in a map.
  5. If the above condition meets, the function will return true, else it will return false.

Implementation

  • C++
  • Java
  • Python
  • JavaScript
  • C#

C++

/* C++ program to check if two given strings are scrambled or not using top down approach of dynamic programming. */
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;


// Declaring an unorderd map for memoization, i.e to store the results for subproblems.
unordered_map<string, bool> mem;


// Function to check if the strings are scrambled.
bool solveScramble(string s1, string s2)
{
// If the size of the string is 1, then S1 and S2 should contain the same character.
if (s1.size() == 1)
return s1 == s2;


// If the strings are equal, they will definitely be scrambled strings.
if (s1 == s2)
return true;


// Calculating a unique map key using * operator, to avoid repetition of keys.
string key = s1 + "*" + s2;


// The key is returned if it is already found in the map.
// This prevents repetition of calculations.
if (mem.find(key) != mem.end())
return mem[key];


int n = s1.size();
bool res = false;


// Loop to check all possible combinations of the strings that can be formed.
for (int i = 1; i < n; ++i)
{
// First check if S2[0..i-1] is a scrambled string of S1[0..i-1] and S2[i..n-1] is a scrambled string of S1[i..n-1].
// If not, check if S2[n-i..n-1] is a scrambled string of S1[0..i-1] and S2[0..i-1] is a scrambled string of S1[n-i..n-1].
// If any of the above conditions hold true, the value of the key will become true.
// This will help in avoiding repeated calculations.
if ((solveScramble(s1.substr(0, i), s2.substr(0, i)) and solveScramble(s1.substr(i), s2.substr(i))) or (solveScramble(s1.substr(0, i), s2.substr(n - i)) and solveScramble(s1.substr(i), s2.substr(0, n - i))))
return mem[key] = true;
}


return mem[key] = false;
}
int main()
{
string s1, s2;


// Taking user input.
cout << "Enter the two strings\n";
cin >> s1 >> s2;


// Calling the function to check the strings.
if (solveScramble(s1, s2))
cout << "Yes the string " << s2 << " is a scramble string of " << s1;
else
cout << "No, the string " << s2 << " is not a scramble string of " << s1;


return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Java

import java.util.HashMap;
import java.util.Scanner;

public class ScrambleString {
static HashMap<String, Boolean> mem = new HashMap<>();

public static boolean solveScramble(String s1, String s2) {
if (s1.length() == 1)
return s1.equals(s2);

if (s1.equals(s2))
return true;

String key = s1 + "*" + s2;

if (mem.containsKey(key))
return mem.get(key);

int n = s1.length();

for (int i = 1; i < n; i++) {
if ((solveScramble(s1.substring(0, i), s2.substring(0, i)) && solveScramble(s1.substring(i), s2.substring(i))) ||
(solveScramble(s1.substring(0, i), s2.substring(n - i)) && solveScramble(s1.substring(i), s2.substring(0, n - i))))
{
mem.put(key, true);
return true;
}
}
mem.put(key, false);
return false;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the two strings:");
String s1 = sc.next();
String s2 = sc.next();

if (solveScramble(s1, s2))
System.out.println("Yes, the string " + s2 + " is a scramble string of " + s1);
else
System.out.println("No, the string " + s2 + " is not a scramble string of " + s1);
}
}
You can also try this code with Online Java Compiler
Run Code

Python

mem = {}

def solve_scramble(s1, s2):
if len(s1) == 1:
return s1 == s2

if s1 == s2:
return True

key = s1 + "*" + s2

if key in mem:
return mem[key]

n = len(s1)

for i in range(1, n):
if (solve_scramble(s1[:i], s2[:i]) and solve_scramble(s1[i:], s2[i:])) or \
(solve_scramble(s1[:i], s2[-i:]) and solve_scramble(s1[i:], s2[:-i])):
mem[key] = True
return True
mem[key] = False
return False


if __name__ == "__main__":
s1 = input("Enter the first string: ")
s2 = input("Enter the second string: ")

if solve_scramble(s1, s2):
print(f"Yes, the string {s2} is a scramble string of {s1}")
else:
print(f"No, the string {s2} is not a scramble string of {s1}")
You can also try this code with Online Python Compiler
Run Code

JavaScript

const mem = {};

function solveScramble(s1, s2) {
if (s1.length === 1) return s1 === s2;

if (s1 === s2) return true;

const key = s1 + "*" + s2;

if (mem[key] !== undefined) return mem[key];

let n = s1.length;

for (let i = 1; i < n; i++) {
if ((solveScramble(s1.substring(0, i), s2.substring(0, i)) && solveScramble(s1.substring(i), s2.substring(i))) ||
(solveScramble(s1.substring(0, i), s2.substring(n - i)) && solveScramble(s1.substring(i), s2.substring(0, n - i))))
{
return mem[key] = true;
}
}
return mem[key] = false;
}

const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});

readline.question('Enter the two strings:\n', (input) => {
const [s1, s2] = input.split(" ");
if (solveScramble(s1, s2))
console.log(`Yes, the string ${s2} is a scramble string of ${s1}`);
else
console.log(`No, the string ${s2} is not a scramble string of ${s1}`);
readline.close();
});
You can also try this code with Online Javascript Compiler
Run Code

C#

using System;
using System.Collections.Generic;

class ScrambleString
{
static Dictionary<string, bool> mem = new Dictionary<string, bool>();

static bool SolveScramble(string s1, string s2)
{
if (s1.Length == 1)
return s1 == s2;

if (s1 == s2)
return true;

string key = s1 + "*" + s2;

if (mem.ContainsKey(key))
return mem[key];

int n = s1.Length;

for (int i = 1; i < n; i++)
{
if ((SolveScramble(s1.Substring(0, i), s2.Substring(0, i)) && SolveScramble(s1.Substring(i), s2.Substring(i))) ||
(SolveScramble(s1.Substring(0, i), s2.Substring(n - i)) && SolveScramble(s1.Substring(i), s2.Substring(0, n - i))))
{
return mem[key] = true;
}
}

return mem[key] = false;
}

static void Main()
{
Console.WriteLine("Enter the two strings:");
string s1 = Console.ReadLine();
string s2 = Console.ReadLine();

if (SolveScramble(s1, s2))
Console.WriteLine($"Yes, the string {s2} is a scramble string of {s1}");
else
Console.WriteLine($"No, the string {s2} is not a scramble string of {s1}");
}
}


Input

Enter the two strings:
actor
rcato


Output

No, the string rcato is not a scramble string of actor.

Time Complexity

The time complexity of this approach is given by O(N2), where is the length of the strings.

Since every combination is computed only once, the time complexity of this approach is given by O(N*N), or simply O(N2).

Space Complexity

The space complexity of this approach is given by O(N2), where is the length of the strings.

Since every combination will be placed in the unordered_map, the space complexity of this approach is given by O(N*N), or simply O(N2). 

Frequently Asked Questions

What is the time complexity of scrambled string?

The time complexity of the solution done by the dynamic programming approach is given by O(N^2), where N is the length of the strings. This is because every single combination we had is computed only once. 

How do you jumble strings in Python?

We can jumble strings in Python using the shuffle() function. The function is present in the ‘random’ module. But the shuffle() function takes a list as input. So we’ll first convert string to list and then, list to string again.

Conclusion

So, this blog discussed two different approaches to solving the problem of Scramble strings and how Dynamic Programming can enhance the flow of the normal algorithm that uses simple recursion.

To learn more, head over right now to Coding Ninjas Studio to practice problems on dynamic programming and strings and crack your interviews like a Ninja!

Check out this article - C++ String Concatenation

Recommended problems -

 

In case of any comments or suggestions, feel free to post them in the comments section.

Live masterclass