Watch 10 video solutions for Scramble String, a hard level problem involving String, Dynamic Programming. This walkthrough by Aditya Verma has 148,906 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: Given two strings s1 and s2, determine whether s2 can be formed by recursively partitioning s1 and swapping its substrings. A scramble operation splits a string into two non-empty parts and optionally swaps them. The task is to check if repeated splits and swaps can transform one string into the other.
Approach 1: Recursive Approach with Memoization (Time: O(n^4), Space: O(n^3))
This approach directly models the recursive definition of a scramble string. For every substring pair (s1[i..j], s2[k..l]), try every possible split point and check two cases: no swap (left-left and right-right) and swap (left-right and right-left). If any partition satisfies the condition recursively, the strings are scramble equivalents. Without optimization the recursion explodes exponentially, so a memoization cache stores results for previously computed substring pairs. This avoids recomputation and turns repeated recursive checks into constant-time lookups. The algorithm still examines many substring partitions, resulting in O(n^4) time.
Before exploring partitions, you can prune impossible branches by checking if the substrings contain the same character frequencies. If the counts differ, they cannot be scrambles. This pruning significantly reduces recursion depth for many inputs. The solution heavily relies on substring comparison and recursion state caching, which makes it a classic example of dynamic programming applied to string problems.
Approach 2: Dynamic Programming (Bottom-Up) (Time: O(n^4), Space: O(n^3))
The bottom-up DP approach removes recursion entirely. Define a 3D DP state dp[len][i][j] that represents whether the substring of length len starting at i in s1 can be scrambled to the substring starting at j in s2. Initialize the base case for len = 1 by comparing characters directly. Then build solutions for larger substring lengths by trying every split position k within the substring.
For each split, check two conditions: the non-swapped configuration (dp[k][i][j] and dp[len-k][i+k][j+k]) and the swapped configuration (dp[k][i][j+len-k] and dp[len-k][i+k][j]). If either holds true, mark the state as valid. Iterating through all lengths, start indices, and split points leads to O(n^4) time. The DP table stores O(n^3) states, giving O(n^3) space complexity. This version is deterministic and avoids recursion overhead.
Recommended for interviews: Start by describing the recursive definition of a scramble string, then implement the memoized recursion. It mirrors the problem statement and shows strong reasoning about overlapping subproblems. If asked for optimization or iterative thinking, explain the bottom-up DP formulation. Interviewers typically expect the memoized solution with correct pruning and complexity analysis.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pure Recursive (Brute Force) | O(2^n) | O(n) | Conceptual understanding of the scramble definition; not practical for large inputs |
| Recursive with Memoization | O(n^4) | O(n^3) | Interview-friendly solution that avoids repeated recursion |
| Bottom-Up Dynamic Programming | O(n^4) | O(n^3) | When you want a deterministic iterative solution without recursion |