Scramble String

Hard
893.

Scramble String

Scramble String is a hard coding problem on strings and dynamic programming, asked in Amazon, Google, Microsoft and Rubrik interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var isScramble = function(s1, s2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Scramble String — Solution in Python, Java & C++

Scramble String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Scramble String is a hard coding problem on strings and dynamic programming, asked in Amazon, Google, Microsoft and Rubrik interviews.

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.

Hints for Scramble String

  1. Hint 1

    Recurse on pairs of substrings, trying every split point.

  2. Hint 2

    At each split, try both the un-swapped and the swapped pairing.

  3. Hint 3

    Prune hard: if two substrings have different character multisets, they can never match.

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

  1. Equal strings match trivially.
  2. If the sorted characters differ, return false — a decisive and cheap prune.
  3. 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).
  4. 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)

Java

private static Map<String, Boolean> scrambleMemo;

private static boolean scrambleGo(String a, String b) {
    if (a.equals(b)) return true;
    String key = a + "#" + b;
    Boolean cached = scrambleMemo.get(key);
    if (cached != null) return cached;
    char[] ca = a.toCharArray();
    char[] cb = b.toCharArray();
    Arrays.sort(ca);
    Arrays.sort(cb);
    if (!Arrays.equals(ca, cb)) {
        scrambleMemo.put(key, false);
        return false;
    }
    int n = a.length();
    for (int i = 1; i < n; i++) {
        if (scrambleGo(a.substring(0, i), b.substring(0, i)) && scrambleGo(a.substring(i), b.substring(i))) {
            scrambleMemo.put(key, true);
            return true;
        }
        if (scrambleGo(a.substring(0, i), b.substring(n - i)) && scrambleGo(a.substring(i), b.substring(0, n - i))) {
            scrambleMemo.put(key, true);
            return true;
        }
    }
    scrambleMemo.put(key, false);
    return false;
}

public static boolean isScramble(String s1, String s2) {
    scrambleMemo = new HashMap<>();
    return scrambleGo(s1, s2);
}

C++

static unordered_map<string, bool> scrambleMemo;

static bool scrambleGo(const string& a, const string& b) {
    if (a == b) return true;
    string key = a + "#" + b;
    auto it = scrambleMemo.find(key);
    if (it != scrambleMemo.end()) return it->second;
    string ca = a, cb = b;
    sort(ca.begin(), ca.end());
    sort(cb.begin(), cb.end());
    if (ca != cb) {
        scrambleMemo[key] = false;
        return false;
    }
    int n = (int) a.size();
    for (int i = 1; i < n; i++) {
        if (scrambleGo(a.substr(0, i), b.substr(0, i)) && scrambleGo(a.substr(i), b.substr(i))) {
            scrambleMemo[key] = true;
            return true;
        }
        if (scrambleGo(a.substr(0, i), b.substr(n - i)) && scrambleGo(a.substr(i), b.substr(0, n - i))) {
            scrambleMemo[key] = true;
            return true;
        }
    }
    scrambleMemo[key] = false;
    return false;
}

bool isScramble(string s1, string s2) {
    scrambleMemo.clear();
    return scrambleGo(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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming