Rearranging String

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:

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.
We can write a recursive function ‘rearrange(string ‘S’, string ‘W’)’ which returns true if it is possible to rearrange ‘S’ to form ‘W’.
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.
If none of the above combinations return true then return false.

Try Problem

Approach 2

We are working with breaking the string into two substrings and again joining them in some order. We can use memoization as we are checking the same pair of substrings multiple times. Thus this problem has optimal substructure and overlapping subproblems.

Therefore we can solve the problem by following dynamic programming algorithm:

Declare 3D bool array of ‘ISREARRANGEMENT[N + 1][N + 1][N + 1]’ and initialize to false.
The state ‘ISREARRANGEMENT[LEN][i][j]’ represents we are considering two strings of length ‘LEN’ starting from index ‘i’ of the first string and index ‘j’ of the second string.
For ‘LEN = 1’ we will initialize ‘ISREARRANGEMENT[1][i][j]’ with true if i’th character of string ‘S’ and jth character of string ‘W’ are equal.
Now for ‘LEN = 2’ to ‘N’ we will iterate and check for substrings of all length as follows:-
- For a particular length ‘LEN’ in string ‘S’ starting point i.e. ‘i’ can be from ‘0’ to ‘N - LEN’ and similarly for ‘W’ starting point i.e. ‘j’ can be from ‘0’ to ‘N - LEN’. For each par of ‘i’ and ‘j’ we can do as follows:-
  - Now we will consider all lengths ‘K’ from ‘1’ to ‘LEN’ - 1 which has already been pre-calculated. So for each ‘K’ we can break it into two cases:-
    - Consider substring of length ‘K’ starting from ‘i’ and ‘j’ and check if it is possible to rearrange.
    - Consider substring of length ‘K’ starting from ‘i’ and ‘j + LEN - K’ and check if it is possible to rearrange.
    - ‘ISREARRANGEMENT[LEN][i][j]’ = (ISREARRANGEMENT[K][i][j] && ISREARRANGEMENT[LEN - K][i + K][j + K]) || (ISREARRANGEMENT[K][i][j + LEN - k] && ISREARRANGEMENT[LEN - K][i + K][j])
Return ‘ISREARRANGEMENT[N][0][0]’.

Try Problem