Skip to main content

99. Scramble String

hardAsked at Snowflake

Determine whether one string can be obtained by recursively partitioning another. Snowflake asks this for recursive partitioning with memoization — same recursion shape as proving plan equivalence under reordering.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this for plan-equivalence discussion.
  • LeetCode Discuss (2025-09)— Reported at Snowflake SDE-II screens.

Problem

We can scramble a string s to get a string t using the following algorithm: if length is 1, stop. Otherwise, split into two non-empty parts s = x + y; optionally swap x and y; recursively scramble x and y. Given two strings s1 and s2 of the same length, return true if s2 is a scrambled string of s1.

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

Approaches

1. Recursive without memo

Try every split; for each, both swap and non-swap. Recurse.

Time
exponential
Space
O(n) recursion
// outline — exponential.

Tradeoff: Exponential. Don't ship.

2. Memoized recursion (optimal)

Memoize on the (s1, s2) pair. Prune via 'must have same multiset' check before recursing.

Time
O(n^4) approximately
Space
O(n^3) memo
function isScramble(s1, s2) {
  const memo = new Map();
  function check(a, b) {
    if (a === b) return true;
    if (a.length !== b.length) return false;
    const key = a + '|' + b;
    if (memo.has(key)) return memo.get(key);
    if ([...a].sort().join('') !== [...b].sort().join('')) {
      memo.set(key, false);
      return false;
    }
    const n = a.length;
    for (let i = 1; i < n; i++) {
      if ((check(a.slice(0, i), b.slice(0, i)) && check(a.slice(i), b.slice(i))) ||
          (check(a.slice(0, i), b.slice(n - i)) && check(a.slice(i), b.slice(0, n - i)))) {
        memo.set(key, true);
        return true;
      }
    }
    memo.set(key, false);
    return false;
  }
  return check(s1, s2);
}

Tradeoff: Memoization on string pairs keeps it polynomial. The sort-check prune avoids unnecessary recursion.

Snowflake-specific tips

Snowflake interviewers want the multiset prune and the memoization. Bonus signal: pivot to plan equivalence — proving two plans produce the same result under operator reordering uses a similar recursive matching with memoization on subplan pairs.

Common mistakes

  • Skipping the sort/multiset prune — exponential without it.
  • Memo key not capturing both strings — false positives or negatives.
  • Slicing in a tight loop without trimming the constant factor.

Follow-up questions

An interviewer at Snowflake may pivot to one of these next:

  • Generate all scrambles of a string.
  • Test bipartite plan equivalence.
  • How does Snowflake test plan equivalence?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why prune with multiset check?

If s1 and s2 don't have the same character multiset, no scramble can transform one to the other. The early exit saves exponential work.

How does this connect to plan equivalence?

Two plan trees are equivalent if they produce the same result — proving requires recursive matching of subplans, sometimes with reordering. The structure mirrors Scramble String.

Practice these live with InterviewChamp.AI

Drill Scramble String and other Snowflake interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →