Scramble String

The difficult part of the Scramble String solution is not recognizing that characters are rearranged. It is preserving the recursive boundaries that made the rearrangement legal.

The answer direction

We need to determine whether s2 can be produced from s1 by repeatedly:

• splitting a substring into two non-empty parts;
• preserving or swapping those parts;
• recursively scrambling both parts.

The question is existential: does at least one legal sequence of decisions transform s1 into s2?

The right strategy is memoized interval recursion:

1. Compare one interval of s1 with one equally long interval of s2.
2. Reject the pair if their character multisets differ.
3. Try every non-empty split of the source interval.
4. Test both target geometries:
   • preserve child order;
   • swap child order.
5. Cache the result for the paired intervals.

This is controlled recursion over two strings. It is not arbitrary permutation generation.

Recognize the interval-split pattern

Several signals point toward interval dynamic programming:

• the input is recursively partitioned;
• both the source and target have moving substring boundaries;
• every state can choose among multiple split points;
• the answer asks whether any decomposition succeeds;
• different recursive partition trees can reach the same pair of intervals.

The useful question is:

Can this interval of s1 be transformed into this interval of s2?

Tracking only one position loses the relationship between source and target. Tracking only character counts accepts rearrangements that no recursive split can produce.

This separates Scramble String from nearby string-DP problems:

• Interleaving String consumes characters from two sources while preserving each source's internal order.
• Edit Distance chooses local edits and minimizes an additive cost.
• Scramble String recursively partitions two intervals and checks whether one of two child arrangements works.

The first source split is the anchor. Every correct recurrence must ask where the resulting children land in the target.

Define the paired-substring state

Use:

dfs(i, j, length)

with this invariant:

dfs(i, j, length) is true exactly when s1[i : i + length] can be scrambled into s2[j : j + length].

The state contains:

• i: start of the source interval;
• j: start of the target interval;
• length: their shared length.

All three fields are necessary. For example:

dfs(2, 4, 3)
dfs(2, 4, 5)

refer to different source and target intervals even though their starting positions match.

For length == 1, no non-empty split is legal. The state succeeds exactly when the two characters are equal:

s1[i] == s2[j]

An interval that already matches character-for-character is also immediately successful. No scrambling operation is required.

Derive the two target geometries

Suppose the current source interval has length length. Choose a split offset k:

1 <= k < length

The source becomes:

source left:  s1[i : i + k]       # length k
source right: s1[i + k : i + length]  # length - k

There are exactly two legal ways for those children to occupy the target interval.

Preserve the child order

The source left child maps to the target left child. The source right child maps to the target right child:

dfs(i,     j,     k)
and
dfs(i + k, j + k, length - k)

The target split occurs at the same offset k.

Swap the child order

The source left child maps to the target suffix, while the source right child maps to the target prefix:

dfs(i,     j + length - k, k)
and
dfs(i + k, j,             length - k)

The target suffix begins at j + length - k because the source left child has length k. It occupies the final k positions of the target interval.

Source:  [ left: k ][ right: length-k ]

Preserve:
         [ left: k ][ right: length-k ]

Swap:
         [ right: length-k ][ left: k ]

The recurrence is:

dfs(i, j, length) =
    any(
        (
            dfs(i, j, k)
            and dfs(i + k, j + k, length - k)
        )
        or
        (
            dfs(i, j + length - k, k)
            and dfs(i + k, j, length - k)
        )
        for k in 1 .. length - 1
    )

The outer operation is OR because one successful split is enough. Each candidate geometry uses AND because both child transformations must succeed.

The preserve and swap branches are not arbitrary special cases. They are the two target alignments induced by one source split.

Prune with character counts

Scrambling changes boundaries and order, but it never changes the multiset of characters in an interval.

For each state, compare the character frequencies in:

s1[i : i + length]
s2[j : j + length]

If any count differs, the state is impossible.

Because the strings contain lowercase English letters, a 26-element balance array is enough:

• increment for each source character;
• decrement for each target character;
• reject if any balance is nonzero.

This is a necessary condition, not a proof.

For example, "great" and "rgeat" have matching counts and do have a valid recursive decomposition. But "abcde" and "caebd" also have matching counts, while no valid scramble transformation exists. Character counts tell us that recursion is worth attempting; the recurrence proves whether the boundaries can align.

The implementation can combine two cheap checks in one scan:

• whether the intervals are already equal;
• whether their character balances match.

If every corresponding character matches, return True immediately. Otherwise, a nonzero balance rejects the state before split enumeration begins.

A prefix-frequency table could make interval count queries constant-time after preprocessing. That is a valid refinement, but the main cost remains: every viable state may still inspect every split. Under the constraint n <= 30, the direct scan is easier to audit and keeps the code close to the derivation.

Memoize the recursive search

Without memoization, recursion repeatedly explores equivalent partition questions. Different split trees can ask whether the same source interval maps to the same target interval.

The complete memo key is:

(i, j, length)

Do not omit any field:

• i alone does not identify the target;
• j alone does not identify the source;
• (i, j) does not identify the interval length;
• an unordered pair loses the direction from source to target.

Top-down recursion fits the problem directly:

• start with the full strings;
• inspect only states reached by candidate splits;
• stop as soon as one geometry succeeds;
• cache both successful and unsuccessful states.

The cache stores only reached states, but O(n^3) remains the upper bound on the number of possible indexed states.

Prove the recurrence correct

The recurrence mirrors the definition of a scramble.

Base case

For a length-one interval, no non-empty split exists. The only legal terminal condition is character equality:

dfs(i, j, 1) == (s1[i] == s2[j])

This is both necessary and sufficient.

Soundness

Assume dfs(i, j, length) returns True through split k.

In the preserve branch:

• the source left interval transforms into the target left interval;
• the source right interval transforms into the target right interval.

In the swap branch:

• the source left interval transforms into the target suffix;
• the source right interval transforms into the target prefix.

Both child states are true, so both child transformations are legal. Preserving or swapping their order is also legal. Combining those operations produces a valid transformation of the parent interval.

Therefore, every returned True result is sound.

Completeness

Assume a valid transformation exists for a state with length > 1.

Its first operation must split the source interval at some non-empty offset k. The loop tests every such offset.

After that split, the children either remain in their original order or swap positions. There are no other legal arrangements at that level. The recurrence tests both geometries and recursively checks both children in each geometry.

By induction on interval length, the corresponding child states return True. The loop therefore finds the valid top-level split and returns True.

Pruning and memoization

Every legal scramble operation rearranges characters without changing their frequencies. A frequency mismatch proves that the state is false, so count pruning is sound.

Memoization does not remove any legal decision. It only reuses the result of a state whose full recurrence has already been evaluated.

Dry-run the target geometry

Start with a parent-level swap:

s1 = "great"
s2 = "eatgr"

At the top level, choose k = 2:

source: gr | eat
target: eat | gr

The preserve branch would ask whether:

"gr"  -> "ea"
"eat" -> "tgr"

The swap branch asks:

"gr"  -> "gr"
"eat" -> "eat"

Using j = 0 and length = 5, the swap calls are:

dfs(0, 3, 2)  # "gr"  -> target suffix "gr"
dfs(2, 0, 3)  # "eat" -> target prefix "eat"

The suffix starts at:

j + length - k = 0 + 5 - 2 = 3

Using j + k would produce target index 2, which is the wrong boundary. This is the indexing error worth catching before writing the recursion.

Now consider the nested case:

s1 = "great"
s2 = "rgeat"

At k = 2, the parent preserves its child order:

source: gr | eat
target: rg | eat

The right child matches directly. The left child "gr" maps to "rg" through its own length-two swap.

A parent does not need to swap for a child to swap. Each recursive interval makes its own preserve-or-swap decision.

For the negative case:

s1 = "abcde"
s2 = "caebd"

The full intervals have matching character counts, so pruning cannot reject them immediately. The algorithm must inspect splits. Some local arrangements may survive, but every complete decomposition eventually fails.

Global character equality gets the search started. Interval structure finishes it.

Implement the Python solution

from functools import cache


class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        n = len(s1)

        @cache
        def dfs(i: int, j: int, length: int) -> bool:
            # State:
            # s1[i:i + length] can scramble into s2[j:j + length].

            if length == 1:
                return s1[i] == s2[j]

            balance = [0] * 26
            same = True

            # Check direct equality and character counts in one pass.
            for offset in range(length):
                source_char = s1[i + offset]
                target_char = s2[j + offset]

                if source_char != target_char:
                    same = False

                balance[ord(source_char) - ord("a")] += 1
                balance[ord(target_char) - ord("a")] -= 1

            if same:
                return True

            if any(value != 0 for value in balance):
                return False

            for k in range(1, length):
                # Preserve child order.
                if (
                    dfs(i, j, k)
                    and dfs(i + k, j + k, length - k)
                ):
                    return True

                # Swap child order.
                if (
                    dfs(i, j + length - k, k)
                    and dfs(i + k, j, length - k)
                ):
                    return True

            return False

        return dfs(0, 0, n)

The code maps directly to the derivation:

• (i, j, length) identifies the paired intervals;
• the length-one branch implements the recursion's stopping rule;
• same handles an already-matching interval;
• balance rejects impossible character multisets;
• the first recursive condition represents preserve;
• the second represents swap;
• @cache stores every completed state, including False.

The most common implementation failures are boundary failures:

1. Allowing k = 0 or k = length
   Those are empty splits and violate the problem definition.

2. Omitting length from the cache key
   Equal start positions can describe different intervals.

3. Using j + k in the swap branch
   The source left child belongs at the target suffix, which begins at j + length - k.

4. Checking character counts only for the full strings
   Every recursive state compares different intervals, so pruning belongs inside dfs.

5. Treating matching counts as the answer
   Counts remove impossible states; they do not prove recursive compatibility.

6. Returning False after one failed split
   A failed geometry says nothing about later split offsets.

Complexity, limits, and edge cases

There are at most O(n^3) possible indexed states:

• O(n) choices for source start i;
• O(n) choices for target start j;
• O(n) choices for shared length.

This is an upper bound. Top-down memoization stores only states reached by the search.

Each reached state can inspect:

• O(length) characters for direct equality and frequency balance;
• up to O(length) split offsets.

Since length <= n, the per-state work is O(n). Across at most O(n^3) states:

Time:  O(n^4)
Space: O(n^3)

The O(n^3) term counts possible memo states. The extra factor comes from scanning split offsets within each state.

The direct character-and-balance scan is also bounded by O(n^4) when summed over all possible states. It can reject many states early, but it does not improve the worst-case asymptotic bound. The implementation avoids substring slicing, so its accounting does not depend on hidden slice-copy costs.

The recursion depth is O(n). In addition to the asymptotic memo storage, Python stores cache keys, tuple objects, and Boolean results, so the practical memory footprint is larger than the label alone suggests.

Useful edge cases include:

Case	What it checks
("a", "a")	length-one success
("a", "b")	length-one failure
identical strings	direct equality shortcut
different character counts	pruning
repeated letters	non-unique boundaries
("great", "rgeat")	nested preserve/swap success
("great", "eatgr")	parent-level swap alignment
("abcde", "caebd")	matching counts but invalid structure
length two	smallest nontrivial split

The constraint n <= 30 matters. This recurrence is appropriate for that bounded input; complexity claims should always be read together with the input contract.

The transferable recognition rule

When a problem recursively partitions one object and asks whether it can match another, define the paired intervals before writing code.

For every source split, ask:

1. Where do the children land if order is preserved?
2. Where do they land if order is swapped?
3. What exact target indices represent those geometries?
4. Which cheap invariant rejects an impossible pair?

Character counts are evidence, not proof. The proof comes from enumerating every legal first split and both legal child arrangements.

My interview checklist is short:

• State exactly what each interval state means.
• Include both start positions and the shared length.
• Draw the target alignment for preserve and swap.
• Make the base case match the operation's stopping rule.
• Enumerate every non-empty split.
• Count states and per-state work separately.
• Test a parent-level swap, not only a nested child swap.

The reusable pattern is paired interval recursion with legal target geometries: split the source, enumerate where the children can go, recurse, and cache. Draw that geometry first. The recurrence is then an inventory of legal first moves.