Skip to main content

87. Scramble String

hard

Determine whether s2 is a scramble of s1, where scrambling means recursively splitting and optionally swapping halves. A purely structural recursion problem — split, branch, memoize.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

We can scramble a string s to get a string t using the following algorithm: If the length of the string is 1, stop. If the length of the string is > 1, do the following: Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y. Randomly decide to swap the two substrings or to keep them in the same order. So, after this step, s may become s = x + y or s = y + x. Apply step 1 recursively on each of the two substrings 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.

Constraints

  • s1.length == s2.length
  • 1 <= s1.length <= 30
  • s1 and s2 consist of lowercase English letters.

Examples

Example 1

Input
s1 = "great", s2 = "rgeat"
Output
true

Example 2

Input
s1 = "abcde", s2 = "caebd"
Output
false

Example 3

Input
s1 = "a", s2 = "a"
Output
true

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If s1 == s2 -> true. If sorted(s1) != sorted(s2) -> false (cheap reject — characters must match).

Hint 2

Try every split point i from 1 to length - 1.

Hint 3

Case 1 (no swap): s1[..i] scrambles to s2[..i] AND s1[i..] scrambles to s2[i..].

Hint 4

Case 2 (swap): s1[..i] scrambles to s2[len-i..] AND s1[i..] scrambles to s2[..len-i]. Memoize on (s1, s2).

Solution approach

Reveal approach

Recursive isScramble(s1, s2): if s1 == s2 return true; if char counts differ, return false (pre-check rejects clearly impossible cases). For each split point i from 1 to length - 1: case 1 (no swap) — recurse on (s1[..i], s2[..i]) and (s1[i..], s2[i..]); case 2 (swap) — recurse on (s1[..i], s2[len-i..]) and (s1[i..], s2[..len-i]). If any combination succeeds, return true. Memoize on (s1, s2) string pair — same input always gives the same answer. Time is O(n^4) memoized (n^2 substring pairs times O(n) split points times O(n) recursion); space O(n^3) for the memo.

Complexity

Time
O(n^4)
Space
O(n^3)

Related patterns

  • recursion
  • memoization
  • string-partition

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon

Practice these live with InterviewChamp.AI

Drill Scramble String and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →