Scramble String

Hard
0/120
Average time to solve is 15m
profile
Contributed by
25 upvotes
Asked in companies
PostmanCiscoRubrik, Inc.

Problem statement

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.
    • Detailed explanation ( Input/output format, Notes, Images )
    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
    Sample Input 1:
    1
5
great rgeat
    Sample Output 1:
    true
    Explanation for Sample Input 1:
    Note that the ‘/’ denotes the division of string.
One of the possible ways in which the operations can be applied on S is:
“great” -> “gr/eat” (Division at random index)
“gr/eat” -> “gr/eat” (Decided not to swap the two substrings and keep them in the same order.)
“gr/eat” -> “g/r / e/at” (Applying the same operation of division at random index recursively on both substrings).
“g/r / e/at” -> “r/g / e/at” (Random choice to swap the first substring and keeping the second substring same.)
“r/g / e/at” -> “r/g / e/ a/t” (Again applying the same algorithm recursively to divide at into a/t.)
“r/g / e/ a/t” -> “r/g / e/ a/t” (Random decision to keep the strings in same order and not swap them.)
Now since the length of all the strings is equal to 1, we stop the algorithm and the result of S = “rgeat” which is equal to T.
Hence return true.
    Sample Input 2:
    2
1
a a
5
pqrst  rptqs
    Sample Output 2:
    true
false
    Explanation for Sample Input 2:
    For the first test case, since both the strings are equal, we return true.

For the second test case, there is no possible sequence of operations to make S equal to T. For example, 
pqrst --> cut p|qrst
p|qrst → cut p, qr|st
p, qr|st --> scramble p, st, qr = pstqr which is scrambled and pq are apart. We cannot scramble rptqs into pqrst because there is no way in which we can cut pqrst such that prefix and suffix are anagrams of the correspondings in rptqs. See:

p | qrst --> 'p' not anagram of 'r' nor 's'
pq | rst --> pq not anagram of rp nor of qs
pqr | st --> pqr not anagram of rpt nor of tqs
pqrs | t --> pqrs not anagram of rptq nor of ptqs

Hence we return false.
    Hint

    Try the simplest possible way.

    Approaches (2)
    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.
    Time Complexity

    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)

    Space Complexity

    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).

    Code Solution
    (100% EXP penalty)
    Scramble String
    Full screen
    Console