Last Updated: 15 Mar, 2021
##### Rearranging String
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
``````
Approaches

## 01Approach

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.