We can scramble a string s to get a string t using the following algorithm:
s, divide it to x and y where s = x + y.s may become s = x + y or s = y + x.x and y.Given two strings s1 and s2 of the same length, return true if s2 is a scrambled string of s1, otherwise, return false.
Example 1:
Input: s1 = "great", s2 = "rgeat" Output: true Explanation: One possible scenario applied on s1 is: "great" --> "gr/eat" // divide at random index. "gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order. "gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them. "g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order. "r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t". "r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order. The algorithm stops now, and the result string is "rgeat" which is s2. As one possible scenario led s1 to be scrambled to s2, we return true.
Example 2:
Input: s1 = "abcde", s2 = "caebd" Output: false
Example 3:
Input: s1 = "a", s2 = "a" Output: true
Constraints:
s1.length == s2.length1 <= s1.length <= 30s1 and s2 consist of lowercase English letters.Scramble String asks whether one string can be transformed into another by recursively partitioning and swapping substrings. A brute force recursive approach tries every possible split position and checks both cases: swapped and non-swapped substrings. However, this leads to heavy recomputation.
The optimized strategy uses recursion with memoization or dynamic programming. For two substrings of equal length, we attempt all partition points and verify if their left and right segments match either directly or after swapping. Memoization stores results for previously checked substring pairs to avoid repeated work.
Another common method is a 3D DP table where dp[i][j][len] represents whether the substring starting at index i in the first string can form the substring starting at index j in the second string with length len. By iterating through substring lengths and split points, we progressively determine valid scrambles.
This approach significantly reduces redundant checks while maintaining manageable complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursion + Memoization | O(n^4) | O(n^3) |
| Bottom-Up Dynamic Programming | O(n^4) | O(n^3) |
Aditya Verma
This approach uses recursion to explore all possible valid splits and checks if either of the permutations exist. To avoid re-computation, use a dictionary to memoize already computed results for specific substrings.
Time Complexity: O(N^4), where N is the length of the strings.
Space Complexity: O(N^3), used by the memoization array.
1var isScramble = function(s1, s2) {
2 const memo = new Map();
3 const hasSameChars = (str1, str2) => {
4 const charCount = new Array(26).fill(0);
5 for (let c of str1) charCount[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
6 for (let c of str2) charCount[c.charCodeAt(0) - 'a'.charCodeAt(0)]--;
7 for (let count of charCount) if (count !== 0) return false;
8 return true;
9 };
10
11 const scramble = (s1, s2) => {
12 const key = `${s1} ${s2}`;
13 if (memo.has(key)) return memo.get(key);
14 if (s1 === s2) return true;
15 if (!hasSameChars(s1, s2)) return false;
16
17 const n = s1.length;
18 for (let i = 1; i < n; i++) {
19 if ((scramble(s1.substring(0, i), s2.substring(0, i)) && scramble(s1.substring(i), s2.substring(i))) ||
20 (scramble(s1.substring(0, i), s2.substring(n - i)) && scramble(s1.substring(i), s2.substring(0, n - i)))) {
21 memo.set(key, true);
22 return true;
23 }
24 }
25 memo.set(key, false);
26 return false;
27 };
28
29 return scramble(s1, s2);
30};The JavaScript solution implements memoization with a Map to track previously computed results. It verifies character frequencies between the strings for early exits. The main recursive function evaluates each partition index and both permutations of swapping and not swapping substrings.
This approach is based on dynamic programming. We set up a 3D table where table[i][j][k] holds true if s1's substring starting at index i with length k is a scrambled string of s2's substring starting at index j.
Time Complexity: O(N^4), where N is the length of the strings.
Space Complexity: O(N^3), due to the 3D DP table.
1class
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Scramble String is considered a classic hard dynamic programming problem and can appear in advanced interview rounds. It tests recursion, DP optimization, and understanding of substring partitioning strategies.
The optimal approach uses recursion with memoization or a bottom-up dynamic programming solution. By storing results for substring comparisons, it avoids redundant computations and significantly improves efficiency over naive recursion.
The difficulty comes from the large number of possible substring partitions and swap combinations. Efficiently pruning repeated computations using memoization or DP is essential to make the solution feasible.
Dynamic programming tables or hash maps for memoization work best. They store intermediate results for substring pairs, allowing the algorithm to reuse previously computed states efficiently.
The Java dynamic programming solution involves a three-dimensional boolean array dp, which records whether snippets of s1 can scramble into snippets of s2. By building up from single characters to full strings, it ensures that all possible scrambles are evaluated efficiently.