Is It a Scramble
A string can be SCRAMBLED by this operation, applied recursively: split it at any point into two non-empty parts, optionally swap the two parts, and scramble each part the same way.
Print yes if the second string can be produced from the first, or no otherwise.
great, rgeat -> yes
abcde, caebd -> no
ab, ba -> yes split into a and b, then swap
## The recurrence
Two strings of length L are scrambles of each other when some split point k works, in
one of two arrangements:
NOT swapped: a[0..k-1] ~ b[0..k-1] and a[k..] ~ b[k..]
SWAPPED: a[0..k-1] ~ b[L-k..] and a[k..] ~ b[0..L-k-1]
The swapped case is the one to write carefully. The first k characters of a are
compared against the LAST k of b, and the rest of a against the FIRST L-k of b.
Getting those offsets wrong gives a solution that passes the non-swapped samples.
## The state
A substring of a and a substring of b of the same length, so three numbers: the start
in a, the start in b, and the shared length.
go(i, j, L)
That is O(n^3) states with O(n) work each, which is O(n^4) overall. At n = 30 that
is around 8 * 10^5, which is why the bound is small.
Without memoisation the recursion is exponential, and this is the clearest example in the
topic of a problem whose entire difficulty is recognising that the same
(start, start, length) triple recurs.
## The pruning that makes it fast in practice
Before recursing, compare the character MULTISETS of the two substrings. If they differ, no scramble exists and the branch dies immediately.
That check is not needed for correctness, and without it many inputs take far longer than
the bound suggests, because the search explores splits that could never have matched. It is
the difference between a solution that passes and one that times out on abcde against
caebd, where the answer is no and every split has to be refuted.
## Why length is not enough as a first check
Equal length is necessary. Equal multisets is necessary. Neither is sufficient:
abcd against bdac answers no despite both, and it is a test.
The operation preserves multisets but not every multiset-preserving rearrangement is reachable, because the splits must nest.
## Boundaries
a against a answers yes, and ab against ab answers yes with no swap at all.
abb against bab answers yes and aabb against abab answers yes, both needing a
swap at a non-central split.
## Cost
Time O(n^4) in the worst case. Space O(n^3) for the memo.