Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

You are given an integer ‘N’ and two strings ‘S’ and 'R' each having size = ‘N’. You can scramble the string ‘S’ to obtain string 'R' using the following operations:

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

2. If the length of the string is equal to 1 then stop.

Your task is to return true if 'R' is a scrambled string of ‘S’ else return false.

Note:

```
1. Both the strings are non-empty and are of the same length.
2. You can apply the above operations any number of times on ‘S’.
3. The operations can only be applied on the string ‘S’.
4. ‘S’ and 'R' consist of lowercase letters only.
```

Detailed explanation

```
1 <= T <= 50
1 <= len(S) <= 30
Where ‘len(S)’ represents the length of the string ‘S’.
Time Limit: 1 sec
```

```
1
5
great rgeat
```

```
true
```

```
Note that the ‘/’ denotes the division of string.
One of the possible ways in which the operations can be applied on S is:
“great” -> “gr/eat” (Division at random index)
“gr/eat” -> “gr/eat” (Decided not to swap the two substrings and keep them in the same order.)
“gr/eat” -> “g/r / e/at” (Applying the same operation of division at random index recursively on both substrings).
“g/r / e/at” -> “r/g / e/at” (Random choice to swap the first substring and keeping the second substring same.)
“r/g / e/at” -> “r/g / e/ a/t” (Again applying the same algorithm recursively to divide at into a/t.)
“r/g / e/ a/t” -> “r/g / e/ a/t” (Random decision to keep the strings in same order and not swap them.)
Now since the length of all the strings is equal to 1, we stop the algorithm and the result of S = “rgeat” which is equal to T.
Hence return true.
```

```
2
1
a a
5
pqrst rptqs
```

```
true
false
```

```
For the first test case, since both the strings are equal, we return true.
For the second test case, there is no possible sequence of operations to make S equal to T. For example,
pqrst --> cut p|qrst
p|qrst → cut p, qr|st
p, qr|st --> scramble p, st, qr = pstqr which is scrambled and pq are apart. We cannot scramble rptqs into pqrst because there is no way in which we can cut pqrst such that prefix and suffix are anagrams of the correspondings in rptqs. See:
p | qrst --> 'p' not anagram of 'r' nor 's'
pq | rst --> pq not anagram of rp nor of qs
pqr | st --> pqr not anagram of rpt nor of tqs
pqrs | t --> pqrs not anagram of rptq nor of ptqs
Hence we return false.
```