Rearranging String

Posted: 15 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You have been given two strings ‘S’ and ‘W’. You need to rearrange ‘S' to obtain ‘W’ using the following operations:-

    If the length of the string is greater than 1:

  • Divide the string into two non-empty strings ‘X’ and ‘Y’ such that ‘S’ = ‘X’ + ‘Y’.
  • You can either swap two substrings or keep them in the same order, i.e., after this operation either S = ‘X’ + ‘Y’ or S = ’Y’ + ‘X’.
  • Apply the first step recursively on ‘X’ and ‘Y’.
    • If the length of the string is 1 then stop.

    Example:
    If ‘S’= “great” and ‘W’= “tagre”, ‘S’ can be rearranged to form ‘W’.
    
    ‘S’ = “gre” + “at” (We choose to swap ‘X’ & ‘Y’)
    ‘S’ = “at” + “gre” 
    Now letting “gre” as it is and applying operation on “at”.
    ‘S’ = “a” + “t” + “gre”
    Swapping “a” and “t”
    ‘S’ = “t” + “a” + “gre”
    Therefore ‘S’ can be rearranged into ‘W’. 
    
    Note:
    Both strings are of the same length and operations can only be applied to string ‘S’.
    
    Input Format:
    The first line contains a single integer ‘T’ representing the number of test cases.
    
    The first line of each test case contains a single integer ‘N’ denoting the length of the string ‘S’ and ‘W'.
    
     The next line of the test case contains two space-separated strings ‘S’ and ‘W’.
    
    Output Format:
    For each test case print ‘True’ if ‘S’ can be rearranged to form ‘W’ else print ‘False’. 
    
    Note:
    You do not need to print anything; it has already been taken care of. Just implement the function.
    
    Constraints:
    1 <= T <= 50
    1 <= N <= 20
    
    Time Limit: 1sec
    
    Approach 1

    We will check through all the possible combinations in which ‘S’ can be rearranged:

     

    1. We can divide the string into two substrings with lengths ‘K’ and ‘N - K’ and check if it is possible to form ‘W’ after certain operations.
    2. We can write a recursive function ‘rearrange(string ‘S’, string ‘W’)’ which returns true if it is possible to rearrange ‘S’ to form ‘W’.
    3. We will iterate over all possible ways in which we can break string ‘S’ into ‘X’ and ‘Y’:-
      • If ‘S’ is equal to ‘W’ we will stop and return true.
      • If ‘S’ is not equal to ‘W’ and the length of ‘S’ is ‘1’ return false.
      • We will try both combinations:
        • If both ‘rearrange(S[0, i - 1], W[0, i - 1])’ and ‘rearrange(S[i, N - 1], W[i, N - 1])’ return true, then we return true.
        • If both ‘rearrange(S[0, i - 1], W[N - i, N - 1])’ and ‘rearrange(S[i, N - 1], W[0, N - i -1])’ return true, then we return true.
    4. If none of the above combinations return true then return false.
    Try Problem