Scramble String — Hard Problem & Solution

A string can be scrambled by this recursive procedure: if its length is more than 1, split it at any position into two non-empty parts, optionally swap the…

Difficulty: Hard
Topics: Strings, Dynamic Programming
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A string can be scrambled by this recursive procedure: if its length is more than 1, split it at any position into two non-empty parts, optionally swap the two parts, and then scramble each part the same way.

Given two strings of equal length, return whether s2 is a scramble of s1.

Example 1

Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: Split "great" into "gr" + "eat", scramble "gr" to "rg", and keep "eat".

Example 2

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

Example 3

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

Constraints

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

How to solve Scramble String

The scramble relation is defined recursively, so the check is too. For a pair of equal-length substrings, try every split position and both orientations; memoise on the pair to avoid the exponential blow-up.

Approach

Equal strings match trivially.
If the sorted characters differ, return false — a decisive and cheap prune.
For each split i: check a[0…i) ~ b[0…i) with a[i…) ~ b[i…), or the swapped a[0…i) ~ b[n-i…) with a[i…) ~ b[0…n-i).
Memoise the result for the pair.

Why it works

The recursion mirrors the definition exactly, so it is complete: any scramble is produced by some split with some orientation. The multiset prune is what makes it fast in practice — most pairs fail it immediately, and without it the branching is unmanageable even with memoisation.

Complexity

Time — O(n⁴) with memoisation
Space — O(n³) states

Pitfalls

Forgetting the swapped orientation misses roughly half the scrambles.
Without memoisation the recursion is exponential and times out at n = 30.
The split must produce two non-empty parts, so i runs from 1 to n - 1.

Reference solution

Python

from functools import lru_cache

def isScramble(s1: str, s2: str) -> bool:
    @lru_cache(maxsize=None)
    def go(a: str, b: str) -> bool:
        if a == b:
            return True
        if sorted(a) != sorted(b):
            return False
        n = len(a)
        for i in range(1, n):
            if go(a[:i], b[:i]) and go(a[i:], b[i:]):
                return True
            if go(a[:i], b[n - i:]) and go(a[i:], b[:n - i]):
                return True
        return False

    return go(s1, s2)

JavaScript

var isScramble = function(s1, s2) {
    var memo = {};
    var go = function(a, b) {
        if (a === b) return true;
        var key = a + "#" + b;
        if (memo[key] !== undefined) return memo[key];
        var ca = a.split("").sort().join("");
        var cb = b.split("").sort().join("");
        if (ca !== cb) { memo[key] = false; return false; }
        var n = a.length;
        for (var i = 1; i < n; i++) {
            if (go(a.slice(0, i), b.slice(0, i)) && go(a.slice(i), b.slice(i))) { memo[key] = true; return true; }
            if (go(a.slice(0, i), b.slice(n - i)) && go(a.slice(i), b.slice(0, n - i))) { memo[key] = true; return true; }
        }
        memo[key] = false;
        return false;
    };
    return go(s1, s2);
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue