Skip to main content
Talentd

Scramble String - Solution & Explanation

HardStringDynamic Programming34 min readAsked at: Amazon, Meta, Google +3
Practice this problem

Problem Statement

We can scramble a string s to get a string t using the following algorithm:

  1. If the length of the string is 1, stop.
  2. 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.

This solution uses a recursive method with memoization to solve the scramble string problem. The base condition checks if the two given substrings are equal. If the memoization array has previously computed the solution for the given problem, it returns that result, which avoids re-computation. The recursive call considers both swapping and not swapping the substrings when partitioning.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N^4), where N is the length of the strings.
Space Complexity: O(N^3), used by the memoization array.

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.

In this C solution, we use a 3D boolean DP array dp with indices [i][j][k] indicating whether a substring starting at index i in s1 and a substring starting at index j in s2 of length k can be scrambles of each other. We fill this array iteratively, considering the divisions of the k-length substring into parts.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N^4), where N is the length of the strings.
Space Complexity: O(N^3), due to the 3D DP table.

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.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

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.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Approach with Memoization

Time Complexity: O(N^4), where N is the length of the strings.
Space Complexity: O(N^3), used by the memoization array.

Dynamic Programming Approach

Time Complexity: O(N^4), where N is the length of the strings.
Space Complexity: O(N^3), due to the 3D DP table.

Memorized Search—
Dynamic Programming (Interval DP)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive with MemoizationO(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.

Video Solution

Scramble string | Dynamic Programming | MCM | Leetcode #87 • Techdose • 29,718 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Scramble String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring