Scramble String
Hard · Dynamic Programming · String · Dynamic Programming
Problem
You can scramble a string s like this:
- If s has length 1, stop.
- Otherwise split it at any point into two non-empty parts x and y, so s = x + y.
- Either keep the order (x + y) or swap the parts (y + x).
- Scramble x and y the same way, independently.
Given two strings s1 and s2 of the same length, return true if s2 can be produced by scrambling s1, and false otherwise.
Examples
Input: s1 = "abcd", s2 = "cdba" Output: true
Split into ab | cd and swap to get cdab, then split ab and swap it to get cdba.
Input: s1 = "abcd", s2 = "bdac" Output: false
The letters match, but no sequence of splits and swaps turns abcd into bdac.
Input: s1 = "a", s2 = "a" Output: true
A single letter cannot be split; the strings are already equal.
Constraints
- len(s1) == len(s2)
- 1 <= len(s1) <= 30
- s1 and s2 contain only lowercase English letters
Approaches
- Baseline: bottom-up table over every length — time O(n⁴), space O(n³)
Follow-up
Bottom-up the DP has n³ states and n splits each, so n = 30 costs under a million steps. The letter-count check does not change the worst case, but it cuts most branches in practice, which is why the top-down version is usually much faster on real inputs.
Related problems
Start free on Cariara · Coding problems · System design studio
