Scramble String
You are given an integer ‘N’ and two strings ‘S’ and 'R' each having size = ‘N’. You can scramble the string ‘S’ to obtain string 'R' using the following operations:

1. If the length of the string is greater than 1:

Select any random index and split the string into two non-empty substrings. For e.g: if the string is ‘S’, then divide it into two non-empty substrings ‘A’ and ‘B’ such that ‘S’ = ‘A’ + ‘B’.

You can choose to swap the two substrings or keep them in the same order, i.e., after this operation string ‘S’ may become either ‘S’ = ‘A’ + ‘B’ or ‘S’ = ‘B’ + ‘A’.

Apply the first step recursively on each of the two strings ‘A’ and ‘B’.

2. If the length of the string is equal to 1 then stop.

Your task is to return true if 'R' is a scrambled string of ‘S’ else return false.

Note:

1. Both the strings are non-empty and are of the same length. 2. You can apply the above operations any number of times on ‘S’. 3. The operations can only be applied on the string ‘S’. 4. ‘S’ and 'R' consist of lowercase letters only.

Input Format:

The first line of the input contains an integer 'T' denoting the number of test cases. The first line of each test case contains an integer ‘N’, denoting the size of the strings. The second line of each test case contains two space-separated strings ‘S’ and 'R'.

Output Format:

For each test case print a single line containing either “true” if the string 'R' is a scrambled string of ‘S’, else “false”.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Scramble String

You are given an integer ‘N’ and two strings ‘S’ and 'R' each having size = ‘N’. You can scramble the string ‘S’ to obtain string 'R' using the following operations:

1. If the length of the string is greater than 1:

Select any random index and split the string into two non-empty substrings. For e.g: if the string is ‘S’, then divide it into two non-empty substrings ‘A’ and ‘B’ such that ‘S’ = ‘A’ + ‘B’.

You can choose to swap the two substrings or keep them in the same order, i.e., after this operation string ‘S’ may become either ‘S’ = ‘A’ + ‘B’ or ‘S’ = ‘B’ + ‘A’.

Apply the first step recursively on each of the two strings ‘A’ and ‘B’.

2. If the length of the string is equal to 1 then stop.

Your task is to return true if 'R' is a scrambled string of ‘S’ else return false.

Note:

1. Both the strings are non-empty and are of the same length.

2. You can apply the above operations any number of times on ‘S’.

3. The operations can only be applied on the string ‘S’.

4. ‘S’ and 'R' consist of lowercase letters only.

Input Format:

The first line of the input contains an integer 'T' denoting the number of test cases.

The first line of each test case contains an integer ‘N’, denoting the size of the strings.

The second line of each test case contains two space-separated strings ‘S’ and 'R'.

Output Format:

For each test case print a single line containing either  “true” if the string 'R' is a scrambled string of ‘S’, else “false”.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= len(S) <= 30

Where ‘len(S)’ represents the length of the string ‘S’.

Time Limit: 1 sec

Accepted Answer

The question asks to determine if string 'R' can be obtained by scrambling string 'S' using certain operations.

The length of both strings 'S' and 'R' should be the same.
The operations can be applied recursively on the substrings of 'S'.
If the length of 'S' is 1, the scrambling process stops.
The strings only contain lowercase letters.

Accepted Answer

this is simple problem based on matrix multiplication concept in recursive function we can start a loop from 1 to length of strings and call again to both part to string with respective part of another string.
remember we have to check one part of one string to both part of another string because that is what a scrambled string means.

Accepted Answer

Recursion

Since there are many possible combinations in which the strings can be scrambled the only way is to use recursion with memoization to calculate the answer.
The main idea is to divide the string 'S' into two substrings with length ‘K’ and ‘LEN - K’, where ‘LEN’ is the length of the original string 'S', and check recursively if the two substrings X = S[0….K - 1] and Y = S[k… LEN - 1] form some scramble to generate 'R'.
Let ISSCRAMBLE('S', 'R') be the recursive function that returns true if 'R' is a scramble of 'S' else it returns false.
Now we will generate all the possible substrings of 'S' and check whether they form a scramble or not.
If 'S' is equal to 'R', then return true. It is the base case. Or if the current 'S' has length = 1, then also we need to return true or false depending upon its equality with its counterpart in 'R'.
Let’s say that we cut the string 'S' at index i. Now there are two options.
1. S[0, i] scrambles into R[0, i] and S[i, N] can scramble into R[i,N].
2. S[0, i] can scramble into R[i + 1, N] and S[i, N] can scramble into R[0, N - i].
For i = 1 to n - 1 do the following:
1. If the first condition stated above is true, i.e., if ISSCRAMBLE(S[0, i - 1], R[0, i - 1]) return true and ISSCRAMBLE(S[i, N - 1] and R[i, N - 1]) also return true, then we return true.
2. Else if the second condition stated above is true, i.e., if ISSCRAMBLE(S[0, i - 1], R[N - i, N - 1]) is true and ISSCRAMBLE(S[i, N - 1] and R[0, N - i]) is true, then we return true.
If after the execution of the above loop, none of the combinations works, we return false.

Space Complexity: O(2^n)Explanation:

O(2 ^ N), where N is the length of the given string.

As recursion runs for the 2 ^ N times so stack will be consuming 2 ^ N memory stack. Hence, overall space complexity will be O(2 ^ N).

Time Complexity: O(2^n)Explanation:

O(2 ^ N), where ‘N’ is the length of the given string.

At each point, we recursively check the two substrings until both of them are single character, which takes time O(2 ^ K + 2 ^ (N - K)), where ‘K’ and ‘N - K’ are the lengths of the two substrings. Hence overall time complexity will be O(2 ^ N)

Accepted Answer

Dynamic Programming (Matrix Chain Multiplication)

Since we are working with cutting down strings and again joining them in some other order, one of the possible approaches is to use dynamic programming technique closely related to the approach for matrix chain multiplication.
We can clearly observe that we are checking the same set if substrings again and again many times and also to check if ‘S’ is a scramble of we check if some substring of ‘S’ is a scramble of some substring of ‘R’. Thus this problem has both optimal substructures and overlapping subproblems.
Let us create a 3D bool array named scramble which will store the state SCRAMBLE[N + 1][N][N]
The state scramble[SZ][IDX1][IDX2] represents we are considering two strings of length ‘SZ’ and ‘IDX1’ is the starting index of the first string and ‘IDX2’ is the starting index of the second string.
Initialize the array to false.
One of the base cases would be to iterate over all the strings of size = 1 in both ‘S’ and ‘R’ and check whether the indexes contain the same character or not. So all the strings of size 1 will be represented by SCRAMBLE[1][i][j].
For i = 0 to N -1 and j = 0 to N -1:
1. If S[i] is equal to R[j] then SCRAMBLE[1][i][j] = 1.
2. Else SCRAMBLE[1][i][j] = 0.
Now after this preprocessing, we can apply the same logic on all possible lengths of different substringsLoop from d = 2 to d = N (d is the length of the substring which we will check ), i = 0 to i = N - d( this variable would fetch all substrings of ‘S’ of length = d; and j = 0 to j = N - d (this variable would fetch all substrings of 'R' of length = d)f.
Now considering all the lengths from k = 1 to k = d -1, there are two possibilities for joining the strings and they are shown below:

1. The first possibility is to take the first part of the first string and second part of the second string and concatenate them into one. Similarly taking the first part of the second string and the second part of the first string and concatenating into one. Hence one of the possible states of the DP can be (SCRAMBLE[k][i + size - k][j] && SCRAMBLE[size - k][i][j + k].

2.Another possibility is to concatenate the first parts of both the strings together and second parts together. Hence another possible state of DP can be SCRAMBLE[k][i][j] && SCRAMBLE[size-k][i+k][j+k].

3.After considering both the possibilities if any one of them returns true, we can consider that state as valid, and hence we can take or of both the possibilities and store it in SCRAMBLE[d][i][j].

4.Hence the final DP state will look like this:

SCRAMBLE[d][i][j] = (SCRAMBLE[k][i + size - k][j] && SCRAMBLE[size - k][i][j + k]) or (SCRAMBLE[k][i][j] && SCRAMBLE[size - k][i + k][j + k])

After the loop ends our answer will be stored at SCRAMBLE[len][0][0].
Refer to code for more clear explanation and implementation.

Space Complexity: O(n^3)Explanation:

O(N ^ 3), where ‘N’ is the length of the given string.

As auxiliary 3 D space is used for storing the solutions. Therefore, overall space complexity will be O(N ^ 3).

Time Complexity: O(n^4)Explanation:

O(N ^ 4), where ‘N’ is the length of the given string.

As 4 nested iterations are running in the solution. Therefore, overall time complexity will be O(N ^ 4).

You are given an integer ‘N’ and two strings ‘S’ and 'R' each having size = ‘N’. You can scramble the string ‘S’ to obtain string 'R' using the following operations:

1. If the length of the string is greater than 1:

Select any random index and split the string into two non-empty substrings. For e.g: if the string is ‘S’, then divide it into two non-empty substrings ‘A’ and ‘B’ such that ‘S’ = ‘A’ + ‘B’.

You can choose to swap the two substrings or keep them in the same order, i.e., after this operation string ‘S’ may become either ‘S’ = ‘A’ + ‘B’ or ‘S’ = ‘B’ + ‘A’.

Apply the first step recursively on each of the two strings ‘A’ and ‘B’.

2. If the length of the string is equal to 1 then stop.

Your task is to return true if 'R' is a scrambled string of ‘S’ else return false.

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Wunderman Thompson Commerce Technical Associate interview questions & answers

Popular interview questions of Technical Associate