Scramble String-Coding question asked by Microsoft, Google, Salesforce, Meta

Problem Statement:

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

We can scramble a string s to get a string t using the following algorithm:

If the length of the string is 1, stop.

If the length of the string is > 1, do the following:

Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y.

Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x.

Apply step 1 recursively on each of the two substrings x and y.

Given two strings s and t of the same length, return true if t is a scrambled string of s, otherwise, return false.

Input Format:

Two strings s and t.

Output Format:

Boolean value.

Sample Input 1:

s1 = “great”, s2 = “rgeat”

Sample Output 1:

True

Sample Input 2:

s1 = “abcde”, s2 = “caebd”

Sample Output 2:

false

Sample Input 3:

s1 = "a", s2 = "a"

Sample Output 3:

true

Explanation:

One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is "rgeat" which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = “great”:

great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.

We say that “rgeat” is a scrambled string of “great”.

rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

Similarly, if we continue to swap the children of nodes “eat” and “at”, it produces a scrambled string “rgtae”.

We say that “rgtae” is a scrambled string of “great”.

rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

Approach 1(Recursive):

Recursion of the string lengths do not equal or the characters are mismatch (use map), we can return false. Since each part can be scrambled, we need recursion to check scramble of left part and right part. As we swap the text, the match for left could also happen on the right side, we need to check the match between left and right as well

Time complexity O(2^n)

Space complexity O(n) due to recursion stack

Code of approach 1:

Approach 2(Dynamic):

We create three dimensional array, dp[][][], where dp[i][j][k] indicate the scrambleof length i and j-th character from s1 and kth character from s2. We need to check every possible breaking point from 1 to i — 1 using a variable b. Left part match left part, and right part match right part, so we check match from j and k with length b, and match from j + b and k + b with length i — b. Left part match right part, and right part match left part, so we check match from j and k + i — b with length b, and match from j + b and k for length i — b

Time complexity O(n⁴)

Space complexity O(n³)

Code for approach 2:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.