87. Scramble String - Solution & Explanation

Q: Is Scramble String easy or hard?

Scramble String is categorized as a hard problem because it combines recursion, pruning, and dynamic programming state design. Many candidates initially attempt brute-force recursion, but recognizing overlapping subproblems and applying memoization is the key challenge.

Q: How to solve Scramble String in O(n)?

Scramble String cannot be solved in O(n) time because the algorithm must examine many substring combinations and partition points. The optimal known solutions use dynamic programming or memoized recursion with O(n^4) time and O(n^3) space.

Q: What is the best approach for Scramble String?

The most common approach uses recursion with memoization. It follows the recursive definition of scrambling by trying every split position and checking both swapped and non-swapped partitions. Memoization stores results for substring pairs, reducing the exponential recursion to roughly O(n^4) time with O(n^3) space.

Q: Is Scramble String asked at Google/Amazon/Meta?

Scramble String is considered a classic hard dynamic programming and recursion problem and has appeared in interviews at large tech companies such as Amazon, Google, and Meta. Interviewers use it to evaluate recursion reasoning, memoization, and DP state design.

Q: What data structure is used in Scramble String?

Typical solutions use a memoization map or a 3D DP array. The memo map stores results for substring pairs, while the DP version uses a table like dp[len][i][j] to represent whether substrings of a given length are scrambled versions of each other.

Q: What is the time complexity of Scramble String?

Both the memoized recursion and dynamic programming solutions run in O(n^4) time. For every substring length and pair of starting indices, the algorithm tries all possible split points. The DP table or memo cache stores O(n^3) states, leading to O(n^3) space complexity.

Q: Scramble String Python or Java solution approach?

In Python or Java, the standard solution uses recursive calls with a hashmap or dictionary for memoization. Each recursive step tries every split index and checks both swap and non-swap cases. The overall complexity remains O(n^4) time with O(n^3) space.

The 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. i.e., 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.

Example 1:

Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is "rgeat" which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.

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.

Approach overview

Problem Overview: You are given two strings of equal length. The task is to determine whether one string can be transformed into the other by repeatedly splitting the string into two non-empty parts and optionally swapping those parts. The structure created by these recursive splits defines whether the strings are valid scrambles of each other.

Approach 1: Recursive Approach with Memoization (Time: O(n^4), Space: O(n^3))

This approach directly models the recursive definition of a scramble string. For every substring pair s1[i...j] and s2[i...j], try splitting at every possible index k. Two cases are checked: no swap (left with left and right with right) and swap (left with right and right with left). A memoization map caches results for substring pairs so repeated states are not recomputed. The recursion explores at most O(n^4) states because each substring pair can try up to n partitions, while memoization reduces exponential branching. This method is intuitive and closely follows the recursive structure of the problem, making it a strong baseline when working with string transformations.

Before recursing, you typically check whether both substrings contain the same character frequencies. If they differ, the branch can be pruned immediately. That small optimization significantly cuts the search space.

Approach 2: Dynamic Programming Approach (Time: O(n^4), Space: O(n^3))

The dynamic programming version removes recursion by building results bottom-up. Define dp[len][i][j] as whether the substring of length len starting at i in s1 is a scramble of the substring starting at j in s2. Base cases occur when len = 1, where characters must match. For longer substrings, iterate over every possible split position k and check the same two scenarios used in recursion: no swap and swapped partitions.

This DP table has three dimensions (length and two start indices). For each state you iterate over all split points, producing O(n^4) time complexity with O(n^3) space. The approach is deterministic and avoids recursion stack overhead, which some interviewers prefer when evaluating mastery of dynamic programming. It is also easier to reason about overlapping subproblems compared to raw recursion.

Recommended for interviews: Start by explaining the recursive structure of the scramble definition, then implement the memoized recursion. It shows clear reasoning about overlapping subproblems and pruning. If the interviewer pushes further, describing the bottom-up DP version demonstrates deeper understanding of DP state design and transition logic.

Approach 1: Recursive Approach with Memoization

This approach uses recursion to explore all possible valid splits and checks if either of the permutations exist. To avoid re-computation, use a dictionary to memoize already computed results for specific substrings.

Python

class Solution:
    def __init__(self):
        self.memo = {}

    def isScramble(self, s1: str, s2: str) -> bool:
        if s1 == s2:
            return True
        if (s1, s2) in self.memo:
            return self.memo[(s1, s2)]
        if sorted(s1) != sorted(s2):
            return False
        n = len(s1)
        for i in range(1, n):
            if (self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:])) or \
               (self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i])):
                self.memo[(s1, s2)] = True
                return True
        self.memo[(s1, s2)] = False
        return False

Java

import java.util.*;

class Solution {
    private Map<String, Boolean> memo = new HashMap<>();

    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2)) return true;
        int n = s1.length();
        String key = s1 + " " + s2;
        if (memo.containsKey(key)) return memo.get(key);
        if (!hasSameChars(s1, s2)) return false;
        for (int i = 1; i < n; i++) {
            if ((isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) ||
                (isScramble(s1.substring(0, i), s2.substring(n - i)) && isScramble(s1.substring(i), s2.substring(0, n - i)))) {
                memo.put(key, true);
                return true;
            }
        }
        memo.put(key, false);
        return false;
    }

    private boolean hasSameChars(String s1, String s2) {
        int[] count = new int[26];
        for (char c : s1.toCharArray()) count[c - 'a']++;
        for (char c : s2.toCharArray()) count[c - 'a']--;
        for (int c : count) if (c != 0) return false;
        return true;
    }
}

C++

#include <string>
#include <unordered_map>
using namespace std;

class Solution {
    unordered_map<string, bool> memo;
public:
    bool isScramble(string s1, string s2) {
        if (s1 == s2) return true;
        int n = s1.size();
        string key = s1 + " " + s2;
        if (memo.count(key)) return memo[key];
        if (!hasSameChars(s1, s2)) return false;
        for (int i = 1; i < n; ++i) {
            if ((isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i))) ||
                (isScramble(s1.substr(0, i), s2.substr(n - i)) && isScramble(s1.substr(i), s2.substr(0, n - i)))) {
                return memo[key] = true;
            }
        }
        return memo[key] = false;
    }
private:
    bool hasSameChars(const string &s1, const string &s2) {
        int charCount[26] = {0};
        for (char c : s1) charCount[c - 'a']++;
        for (char c : s2) charCount[c - 'a']--;
        for (int count : charCount) if (count != 0) return false;
        return true;
    }
};

JavaScript

var isScramble = function(s1, s2) {
    const memo = new Map();
    const hasSameChars = (str1, str2) => {
        const charCount = new Array(26).fill(0);
        for (let c of str1) charCount[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        for (let c of str2) charCount[c.charCodeAt(0) - 'a'.charCodeAt(0)]--;
        for (let count of charCount) if (count !== 0) return false;
        return true;
    };

    const scramble = (s1, s2) => {
        const key = `${s1} ${s2}`;
        if (memo.has(key)) return memo.get(key);
        if (s1 === s2) return true;
        if (!hasSameChars(s1, s2)) return false;

        const n = s1.length;
        for (let i = 1; i < n; i++) {
            if ((scramble(s1.substring(0, i), s2.substring(0, i)) && scramble(s1.substring(i), s2.substring(i))) ||
                (scramble(s1.substring(0, i), s2.substring(n - i)) && scramble(s1.substring(i), s2.substring(0, n - i)))) {
                memo.set(key, true);
                return true;
            }
        }
        memo.set(key, false);
        return false;
    };

    return scramble(s1, s2);
};

#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

int memo[31][31][31];

bool scrambleUtil(const char* s1, const char* s2, int i1, int i2, int length) {
    if (strncmp(s1 + i1, s2 + i2, length) == 0) {
        return true;
    }
    if (memo[i1][i2][length] != -1) {
        return memo[i1][i2][length];
    }
    for (int i = 1; i < length; i++) {
        if ((scrambleUtil(s1, s2, i1, i2, i) && scrambleUtil(s1, s2, i1 + i, i2 + i, length - i)) ||
            (scrambleUtil(s1, s2, i1, i2 + length - i, i) && scrambleUtil(s1, s2, i1 + i, i2, length - i))) {
            memo[i1][i2][length] = 1;
            return true;
        }
    }
    memo[i1][i2][length] = 0;
    return false;
}

bool isScramble(char* s1, char* s2) {
    int n = strlen(s1);
    if (n != strlen(s2)) {
        return false;
    }
    memset(memo, -1, sizeof(memo));
    return scrambleUtil(s1, s2, 0, 0, n);
}

using System;
using System.Collections.Generic;

public class Solution {
    private Dictionary<string, bool> memo = new Dictionary<string, bool>();

    public bool IsScramble(string s1, string s2) {
        if (s1 == s2) return true;
        if (s1.Length != s2.Length) return false;

        string key = s1 + " " + s2;
        if (memo.ContainsKey(key)) return memo[key];
        if (!HasSameChars(s1, s2)) return false;

        int n = s1.Length;
        for (int i = 1; i < n; ++i) {
            if ((IsScramble(s1.Substring(0, i), s2.Substring(0, i)) && IsScramble(s1.Substring(i), s2.Substring(i))) ||
                (IsScramble(s1.Substring(0, i), s2.Substring(n - i)) && IsScramble(s1.Substring(i), s2.Substring(0, n - i)))) {
                memo[key] = true;
                return true;
            }
        }
        memo[key] = false;
        return false;
    }

    private bool HasSameChars(string s1, string s2) {
        int[] count = new int[26];
        foreach (char c in s1) count[c - 'a']++;
        foreach (char c in s2) count[c - 'a']--;
        foreach (int c in count) if (c != 0) return false;
        return true;
    }
}

This Python solution uses recursion with memoization, checking all possible partition indices and both possible scrambling options. It uses a dictionary for memoization, speeding up repeated queries. Sorting ensures a quick early rejection of incongruent strings.

Complexity

Time Complexity: O(N^4)
Space Complexity: O(N^3), due to memoization.

Try this approach in the editor

Approach 2: Dynamic Programming Approach

This approach is based on dynamic programming. We set up a 3D table where table[i][j][k] holds true if s1's substring starting at index i with length k is a scrambled string of s2's substring starting at index j.

Python

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        if s1 == s2:
            return True
        if sorted(s1) != sorted(s2):
            return False
        n = len(s1)
        dp = [[[False] * (n + 1) for _ in range(n)] for _ in range(n)]

        for i in range(n):
            for j in range(n):
                dp[i][j][1] = (s1[i] == s2[j])

        for length in range(2, n + 1):
            for i in range(n - length + 1):
                for j in range(n - length + 1):
                    for k in range(1, length):
                        if (dp[i][j][k] and dp[i + k][j + k][length - k]) or \
                           (dp[i][j + length - k][k] and dp[i + k][j][length - k]):
                            dp[i][j][length] = True
                            break

        return dp[0][0][n]

Java

class Solution {
    public boolean isScramble(String s1, String s2) {
        int n = s1.length();
        if (s1.equals(s2)) return true;
        if (!new String(s1).chars().sorted().toArray().equals(new String(s2).chars().sorted().toArray())) return false;

        boolean[][][] dp = new boolean[n][n][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j][1] = s1.charAt(i) == s2.charAt(j);
            }
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                for (int j = 0; j <= n - len; j++) {
                    for (int k = 1; k < len; k++) {
                        if ((dp[i][j][k] && dp[i + k][j + k][len - k]) ||
                            (dp[i][j + len - k][k] && dp[i + k][j][len - k])) {
                            dp[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }

        return dp[0][0][n];
    }
}

C++

#include <string>
using namespace std;

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int n = s1.size();
        if (s1 == s2) return true;
        if (!hasSameChars(s1, s2)) return false;

        bool dp[n][n][n+1];
        memset(dp, false, sizeof(dp));

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j][1] = (s1[i] == s2[j]);
            }
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                for (int j = 0; j <= n - len; j++) {
                    for (int k = 1; k < len; k++) {
                        if ((dp[i][j][k] && dp[i+k][j+k][len-k]) ||
                            (dp[i][j+len-k][k] && dp[i+k][j][len-k])) {
                            dp[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[0][0][n];
    }

private:
    bool hasSameChars(const string &s1, const string &s2) {
        int charCount[26] = {0};
        for (char c : s1) charCount[c - 'a']++;
        for (char c : s2) charCount[c - 'a']--;
        for (int count : charCount) if (count != 0) return false;
        return true;
    }
};

JavaScript

var isScramble = function(s1, s2) {
    const n = s1.length;
    if (s1 === s2) return true;
    if ([...s1].sort().join('') !== [...s2].sort().join('')) return false;
    const dp = Array.from({ length: n }, () => Array.from({ length: n }, () => Array(n+1).fill(false)));

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            dp[i][j][1] = s1[i] === s2[j];
        }
    }

    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            for (let j = 0; j <= n - len; j++) {
                for (let k = 1; k < len; k++) {
                    if ((dp[i][j][k] && dp[i + k][j + k][len - k]) ||
                        (dp[i][j + len - k][k] && dp[i + k][j][len - k])) {
                        dp[i][j][len] = true;
                        break;
                    }
                }
            }
        }
    }

    return dp[0][0][n];
};

#include <string.h>
#include <stdbool.h>

bool isScramble(char* s1, char* s2) {
    int len = strlen(s1);
    if (strcmp(s1, s2) == 0) return true;
    if (len != strlen(s2)) return false;

    bool dp[len][len][len + 1];
    memset(dp, 0, sizeof(dp));

    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            dp[i][j][1] = (s1[i] == s2[j]);
        }
    }

    for (int k = 2; k <= len; k++) {
        for (int i = 0; i <= len - k; i++) {
            for (int j = 0; j <= len - k; j++) {
                for (int q = 1; q < k; q++) {
                    if ((dp[i][j][q] && dp[i + q][j + q][k - q]) ||
                        (dp[i][j + k - q][q] && dp[i + q][j][k - q])) {
                        dp[i][j][k] = true;
                        break;
                    }
                }
            }
        }
    }

    return dp[0][0][len];
}

using System;

public class Solution {
    public bool IsScramble(string s1, string s2) {
        int n = s1.Length;
        if (s1 == s2) return true;
        char[] sorted1 = s1.ToCharArray();
        Array.Sort(sorted1);
        char[] sorted2 = s2.ToCharArray();
        Array.Sort(sorted2);
        if (!new String(sorted1).Equals(new String(sorted2))) return false;

        bool[,,] dp = new bool[n, n, n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j, 1] = s1[i] == s2[j];
            }
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                for (int j = 0; j <= n - len; j++) {
                    for (int k = 1; k < len; k++) {
                        if ((dp[i, j, k] && dp[i + k, j + k, len - k]) ||
                            (dp[i, j + len - k, k] && dp[i + k, j, len - k])) {
                            dp[i, j, len] = true;
                            break;
                        }
                    }
                }
            }
        }

        return dp[0, 0, n];
    }
}

The Python dynamic programming solution uses a 3D list to track potential scrambles from smaller substrings growing up to the full length. It verifies equality between character sets for early exit strategy and leverages the 3D structure to verify combinations of partitions for both swapped and unswapped scenarios.

Complexity

Time Complexity: O(N^4)
Space Complexity: O(N^3), resulting from the 3D DP list.

Try this approach in the editor

Approach 3: Memorized Search

We design a function dfs(i, j, k), which means whether the substring starting from i with length k in s_1 can be converted into the substring starting from j with length k in s_2. If it can be converted, return true, otherwise return false. The answer is dfs(0, 0, n), where n is the length of the string.

The calculation method of function dfs(i, j, k) is as follows:

If k=1, then we only need to judge whether s_1[i] and s_2[j] are equal. If they are equal, return true, otherwise return false;
If k \gt 1, we enumerate the length of the split part h, then there are two cases: if the two substrings of the split are not swapped, then it is dfs(i, j, h) \land dfs(i+h, j+h, k-h); if the two substrings of the split are swapped, then it is dfs(i, j+k-h, h) \land dfs(i+h, j, k-h). If one of the two cases is true, then dfs(i, j, k) is true, return true, otherwise return false.

Finally, we return dfs(0, 0, n).

In order to avoid repeated calculation, we can use memory search.

The time complexity is O(n^4), and the space complexity is O(n^3). Where n is the length of the string.

TypeScript

function isScramble(s1: string, s2: string): boolean {
    const n = s1.length;
    const f = new Array(n)
        .fill(0)
        .map(() => new Array(n).fill(0).map(() => new Array(n + 1).fill(-1)));
    const dfs = (i: number, j: number, k: number): boolean => {
        if (f[i][j][k] !== -1) {
            return f[i][j][k] === 1;
        }
        if (k === 1) {
            return s1[i] === s2[j];
        }
        for (let h = 1; h < k; ++h) {
            if (dfs(i, j, h) && dfs(i + h, j + h, k - h)) {
                return Boolean((f[i][j][k] = 1));
            }
            if (dfs(i + h, j, k - h) && dfs(i, j + k - h, h)) {
                return Boolean((f[i][j][k] = 1));
            }
        }
        return Boolean((f[i][j][k] = 0));
    };
    return dfs(0, 0, n);
}

func isScramble(s1 string, s2 string) bool {
	n := len(s1)
	f := make([][][]int, n)
	for i := range f {
		f[i] = make([][]int, n)
		for j := range f[i] {
			f[i][j] = make([]int, n+1)
		}
	}
	var dfs func(i, j, k int) bool
	dfs = func(i, j, k int) bool {
		if k == 1 {
			return s1[i] == s2[j]
		}
		if f[i][j][k] != 0 {
			return f[i][j][k] == 1
		}
		f[i][j][k] = 2
		for h := 1; h < k; h++ {
			if (dfs(i, j, h) && dfs(i+h, j+h, k-h)) || (dfs(i+h, j, k-h) && dfs(i, j+k-h, h)) {
				f[i][j][k] = 1
				return true
			}
		}
		return false
	}
	return dfs(0, 0, n)
}

Try this approach in the editor

Approach 4: Dynamic Programming (Interval DP)

We define f[i][j][k] as whether the substring of length k starting from i of string s_1 can be transformed into the substring of length k starting from j of string s_2. Then the answer is f[0][0][n], where n is the length of the string.

For substring of length 1, if s_1[i] = s_2[j], then f[i][j][1] = true, otherwise f[i][j][1] = false.

Next, we enumerate the length k of the substring from small to large, and enumerate i from 0, and enumerate j from 0. If f[i][j][h] \land f[i + h][j + h][k - h] or f[i][j + k - h][h] \land f[i + h][j][k - h] is true, then f[i][j][k] is also true.

Finally, we return f[0][0][n].

The time complexity is O(n^4), and the space complexity is O(n^3). Where n is the length of the string.

TypeScript

function isScramble(s1: string, s2: string): boolean {
    const n = s1.length;
    const f = new Array(n)
        .fill(0)
        .map(() => new Array(n).fill(0).map(() => new Array(n + 1).fill(false)));
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            f[i][j][1] = s1[i] === s2[j];
        }
    }
    for (let k = 2; k <= n; ++k) {
        for (let i = 0; i <= n - k; ++i) {
            for (let j = 0; j <= n - k; ++j) {
                for (let h = 1; h < k; ++h) {
                    if (f[i][j][h] && f[i + h][j + h][k - h]) {
                        f[i][j][k] = true;
                        break;
                    }
                    if (f[i + h][j][k - h] && f[i][j + k - h][h]) {
                        f[i][j][k] = true;
                        break;
                    }
                }
            }
        }
    }
    return f[0][0][n];
}

func isScramble(s1 string, s2 string) bool {
	n := len(s1)
	f := make([][][]bool, n)
	for i := range f {
		f[i] = make([][]bool, n)
		for j := 0; j < n; j++ {
			f[i][j] = make([]bool, n+1)
			f[i][j][1] = s1[i] == s2[j]
		}
	}
	for k := 2; k <= n; k++ {
		for i := 0; i <= n-k; i++ {
			for j := 0; j <= n-k; j++ {
				for h := 1; h < k; h++ {
					if (f[i][j][h] && f[i+h][j+h][k-h]) || (f[i+h][j][k-h] && f[i][j+k-h][h]) {
						f[i][j][k] = true
						break
					}
				}
			}
		}
	}
	return f[0][0][n]
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Recursive Approach with Memoization	Time Complexity: O(N^4) Space Complexity: O(N^3), due to memoization.
Dynamic Programming Approach	Time Complexity: O(N^4) Space Complexity: O(N^3), resulting from the 3D DP list.
Memorized Search	–
Dynamic Programming (Interval DP)	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive with Memoization	O(n^4)	O(n^3)	Best for explaining the recursive definition of scramble strings and quickly implementing a top-down solution.
Dynamic Programming (Bottom-Up)	O(n^4)	O(n^3)	Preferred when avoiding recursion or when demonstrating strong DP state modeling in interviews.

Frequently asked questions

Is Scramble String easy or hard?

Scramble String is categorized as a hard problem because it combines recursion, pruning, and dynamic programming state design. Many candidates initially attempt brute-force recursion, but recognizing overlapping subproblems and applying memoization is the key challenge.

How to solve Scramble String in O(n)?

Scramble String cannot be solved in O(n) time because the algorithm must examine many substring combinations and partition points. The optimal known solutions use dynamic programming or memoized recursion with O(n^4) time and O(n^3) space.

What is the best approach for Scramble String?

The most common approach uses recursion with memoization. It follows the recursive definition of scrambling by trying every split position and checking both swapped and non-swapped partitions. Memoization stores results for substring pairs, reducing the exponential recursion to roughly O(n^4) time with O(n^3) space.

Is Scramble String asked at Google/Amazon/Meta?

Scramble String is considered a classic hard dynamic programming and recursion problem and has appeared in interviews at large tech companies such as Amazon, Google, and Meta. Interviewers use it to evaluate recursion reasoning, memoization, and DP state design.

What data structure is used in Scramble String?

Typical solutions use a memoization map or a 3D DP array. The memo map stores results for substring pairs, while the DP version uses a table like dp[len][i][j] to represent whether substrings of a given length are scrambled versions of each other.

What is the time complexity of Scramble String?

Both the memoized recursion and dynamic programming solutions run in O(n^4) time. For every substring length and pair of starting indices, the algorithm tries all possible split points. The DP table or memo cache stores O(n^3) states, leading to O(n^3) space complexity.

Scramble String Python or Java solution approach?

In Python or Java, the standard solution uses recursive calls with a hashmap or dictionary for memoization. Each recursive step tries every split index and checks both swap and non-swap cases. The overall complexity remains O(n^4) time with O(n^3) space.

Scramble String solution and explanation

The problem

Approach overview

Approach 1: Recursive Approach with Memoization

Approach 2: Dynamic Programming Approach

Approach 3: Memorized Search

Approach 4: Dynamic Programming (Interval DP)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Scramble String solution and explanation

The problem

Approach overview

Approach 1: Recursive Approach with Memoization

Approach 2: Dynamic Programming Approach

Approach 3: Memorized Search

Approach 4: Dynamic Programming (Interval DP)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems