New update is available. Click here to update.

Last Updated: 15 Mar, 2021

Moderate

- If the length of the string is greater than 1:

- 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β.
```

```
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β.
```

```
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
```

Approaches

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.

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])

- 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:-

- 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:-
- Return βISREARRANGEMENT[N][0][0]β.