Update appNew update is available. Click here to update.

Rearranging String

Posted: 15 Mar, 2021
Difficulty: Moderate


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.

    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’. 
    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’. 
    You do not need to print anything; it has already been taken care of. Just implement the function.
    1 <= T <= 50
    1 <= N <= 20
    Time Limit: 1sec