Rearranging String

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
3 upvotes
Asked in companies
WalmartAppleAmazon

Problem statement

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’.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5
abcde edabc
5
great bagre
Sample Output 1:
True
False

Explanation Of Sample Input 1:

Test case 1:
We can break “abcde” into “abc” and “de”. We swap two strings now we recursively apply the operation on “abc” and “de”. Since we want “abc” to be equivalent to “abc” we can leave it as it is. We will break “de” into “d” and “e”. We swap two strings because we want them to be equivalent. Finally, we have “edabc”.

Therefore the answer is “True”.

Test case 2:

‘s’ does not contain ‘b’ whereas ‘w’ contains ‘b’. Therefore it is impossible to rearrange ‘s’ to form ‘w’.

Therefore the answer is “False”.
Sample Input 2:
2
1
b b
2
ab bac
Sample Output 2:
True
False

Explanation Of Sample Input 2:

Test case 1:
The given strings are same only and therefore the answer is “True”.

Test case 2:
‘s’ does not contain ‘c’ whereas ‘w’ contains ‘c’. Therefore it is impossible to rearrange ‘s’ to form ‘w’. Therefore the answer is “False”.
Hint

Try to iterate all possible combinations.

Approaches (2)
Recursion Approach

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.
Time Complexity

O(5^N), where ‘N’ denotes the length of the string.

 

As we are recursively calling each sub problem to get the answer of big problem. Each sub problem is divided into 5 subproblem and thus, overall time complexity is O(5^N).

Space Complexity

O(N), where ‘N’ denotes the length of the string.

 

As we recurse a stack of size ‘N’ gets built to store strings. Thus, space complexity is O(N).

Code Solution
(100% EXP penalty)
Rearranging String
Full screen
Console