# Rearranging String

Posted: 15 Mar, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

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