# Scramble String

## 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 optimization 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.

This blog will discuss one such problem, Scramble String, which can easily be solved using recursion. This is not the optimized approach as it might give the error of time limit exceed 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 optimize the time and space complexity, and to check whether the string is a scrambled string or not, we will use dynamic programming.

__Problem Statement__

__Problem Statement__You are given * 2 *strings

*and*

**S1***and the task is to determine whether*

**S2,***is a scrambled form of string*

**S2***or not.*

**S1****Now you may wonder what a scrambled string exactly is???**

We may represent a string * S *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.

We basically split the string into * 2 *non-empty substrings by choosing a random index of a string

*and dividing it into*

**S***halves, say*

**2***and*

**A***.*

**B**So if we use * A* and

*to reconstruct our original string*

**B***, there are*

**S***possibilities:*

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

__Example__

__Example__

**S1 = “ACTIVE“**

**S2 = “EVITAC”**

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

In this example, we see that we can divide the word “**ACTIVE**” into * 2* halves of length

*and*

**2***and these*

**3***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*

**2***character left in them.*

**1**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”**

In this case, string** S2 **is not a scrambled form of **S1 **as** R **and **C **being adjacent is not possible.

Having understood the problem, move ahead to * CodeStudio* 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__

__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
, the total number of partition points is equal to**N**. For example,**N - 1**

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

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

__Primary Condition__

__Primary Condition__

Since we are given * 2 *strings,

*and*

**S1***of equal length*

**S2,***we have to find an index*

**N,***such that at least one of the following holds:*

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

In other words, the first* i * characters of

*should be equal to the first*

**S2***characters of*

**i***and the last*

**S1,***characters of*

**N - i***should be equal to the last*

**S2***characters of*

**N - i**

**S1.*** *2.

*is a scrambled string of*

**S2[N - i. . . N - 1]****S1[0. . .i - 1]**and

*is a scrambled string of*

**S2[0. . . i - 1]**

**S1[N - i . . .N - 1].**In other words, the last * N - i *characters of

*should be equal to the first*

**S2***characters of*

**i***and the first*

**S1***characters of*

**i***should be equal to the last*

**S2***characters of*

**N - i**

**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
else it will return**true,****false.**

### Implementation

```
/* 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;
}
```

__Input__

__Input__

```
Enter the two strings:
active
evitac
```

__Output__

__Output__

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

### Time Complexity

The time complexity of this technique is given by * O(2^{N})* where

*is the length of either of the*

**N***strings.*

**2**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(2^{N})*.

### Space Complexity

The space complexity is given by * O(N) *where

*is the length of either of the*

**N***strings.*

**2**Since recursion uses a call stack, there will be * N^{ }* calls to the function, and hence the space complexity is given by

**O(N).**## 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

- Create a recursive function that will check if the given strings are scrambled or not.
- We will maintain a
memoization array or a simple unordered hash map of type**2-D**>, i.e., the value will either be**<string, bool**or**true**, 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.**false** - If the strings are equal, the function will always return
**true**. - If not, we will try all possible combinations of partitioning the string by calling the function and storing the values in a map.
- If the above condition meets, the function will return
**true**,**false**.

### Implementation

```
/* 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;
}
```

__Input__

__Input__

```
Enter the two strings:
actor
rcato
```

__Output__

__Output__

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

### Time Complexity

The time complexity of this approach is given by* O(N^{2}), *where

*is the length of the strings.*

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

**O(N**^{2}).### Space Complexity

The space complexity of this approach is given by* O(N^{2}), *where

*is the length of the strings.*

**N**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(N**^{2}).## Key Takeaways

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* ** CodeStudio* to practice problems on dynamic programming and strings and crack your interviews like a Ninja!

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

**By Ishita Chawla**

Comments

## No comments yet

## Be the first to share what you think