Scramble String - Solution & Explanation

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.