Scramble String

Scramble String

What is this problem about?

The Scramble String interview question models a recursive string scrambling process. A string s can be "scrambled" into t if you can split s into two non-empty parts at any position, optionally swap the two parts, and recursively scramble each part. Given strings s and t of equal length, determine if t is a scrambled version of s. This is a 3D dynamic programming or memoized recursion problem.

Why is this asked in interviews?

Darwinbox, Meta, Rubrik, Amazon, Google, and Bloomberg ask this HARD problem because it tests complex DP with string interval states. It models the recursive structure of parsing trees and expression rewriting — directly relevant to compiler construction and formal language theory. The memoization key is a tuple of three values: the starting indices and length of the substrings, making it a challenging but educational DP problem.

Algorithmic pattern used

The pattern is memoized recursion (top-down DP). Define isScramble(s1, s2). Base case: if s1 == s2, return true. Pruning: if sorted characters differ, return false (necessary condition). Recursive case: for each split point k in [1, n-1], check two scenarios: (1) no swap: isScramble(s1[:k], s2[:k]) and isScramble(s1[k:], s2[k:]). (2) swap: isScramble(s1[:k], s2[n-k:]) and isScramble(s1[k:], s2[:n-k]). Cache results using (s1, s2) or index+length tuples.

Example explanation

s = "gr", t = "rg".

• Split at k=1: no swap: isScramble("g","r") and isScramble("r","g") — "g"≠"r" → false.
• Split at k=1: swap: isScramble("g","g") and isScramble("r","r") — both true!

Return true ("gr" scrambled to "rg" by swapping single characters).

s = "great", t = "rgeat":

• Multiple splits and swaps lead to true (the split-and-swap tree matches).

Common mistakes candidates make

• Not adding the sorted-character check as a pruning condition — without it, the recursion explores many invalid branches.
• Using the pair (s1, s2) as a memoization key (correct but potentially slow for long strings due to string creation) — index-based memoization is more efficient.
• Forgetting the swap scenario in the recursive case (only checking no-swap), causing false negatives.
• Not understanding why sorted characters being different is a valid early termination: scrambling preserves the multiset of characters.

Interview preparation tip

For the Scramble String coding problem, the string and dynamic programming interview pattern with memoized recursion is the approach. The sorted-character check is crucial pruning. Google and Bloomberg interviewers often ask about the time complexity — O(n^4) with memoization (n^3 states × n split points). Practice explaining the two-case recursion (swap vs no-swap) clearly before coding — it is the core of this problem and distinguishes strong candidates.