String Partitioning

Many string problems ask you to cut a string into pieces that each follow a rule: every piece a palindrome, the pieces forming a Fibonacci-like sequence, four pieces forming an IP address. The choice at each step is where the next cut goes. Grow the next piece one character at a time, and recurse on the rest of the string only when the piece is valid.

The idea#

From position index, the next piece is s[index:i + 1] for each i from index to the end:

1. Choices: every possible end i of the next piece.
2. Hard stop: a piece that breaks a rule. Use continue if a longer piece might still be valid, and break if no longer piece can be.
3. Goal: index == len(s), meaning the whole string has been cut into valid pieces (plus any count rule, such as "at least 3 numbers").

Why it works: you only recurse after a valid piece, so every path that reaches the end of the string is a valid partition. Every partition is one sequence of cut positions, so the loop over i reaches all of them.

The number of possible cut patterns sets the cost. A string of length N has N − 1 gaps, and each can be cut or not, so there are up to $2^{N-1}$ ways to partition it. With $O(N)$ work per partition (checking a piece, copying the path), that's $O(N \cdot 2^N)$.

break vs continue#

The hard stop in step 2 is where most of the pruning happens, and it comes down to break or continue. Ask one question: can a longer piece fix the rule the current piece breaks?

How to spot it#

These cues point to string partitioning.

• "Partition the string so that every substring is…".
• "Split the digits into a sequence where…", "restore", "insert separators".
• Return all partitions, or decide whether one exists.
• Rules on each piece: palindrome, numeric range, no leading zeros, in a dictionary.

Template#

The template follows the three steps above: grow the next piece, apply the break and continue rules, and recurse only on valid pieces.

track(index):
    if index == length of s:           # whole string cut into valid pieces
        record a copy of path
        return
    for i from index to length of s - 1:
        piece = s[index .. i]
        if piece breaks a rule and longer pieces can't fix it: break
        if piece breaks a rule: continue   # a longer piece may still pass
        append piece to path
        track(i + 1)
        pop from path
track(0)

When one split is enough#

Some problems need only one valid split. Make track return True at the goal and write if track(i + 1): return True in the loop. The search then stops on the first success instead of collecting every split.

Pitfalls#

Most of these come up in the numeric variants, where each piece is read as a number.

• Missing the leading-zero rule. "0" is valid; "01" is not.
• An off-by-one bound. The largest signed 32-bit value is $2^{31} - 1$, so the check is val > 2**31 - 1, not val > 2**31.
• continue where break is safe. It still gives the right answer, but explores pieces that can never work.
• Collecting every split when one is enough. Return early on the first success.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Palindrome Partitioning.

• 131. Palindrome Partitioning
• 306. Additive Number
• 842. Split Array into Fibonacci Sequence
• 93. Restore IP Addresses
• 140. Word Break II

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• The choice is where the next cut goes; grow the piece one character at a time.
• Recurse only when the current piece is valid.
• continue when a longer piece could still pass, break when it can't.
• Partitioning a string of length N is $O(N \cdot 2^N)$ in the worst case.
• Leading zeros and numeric bounds ($2^{31} - 1$, 255) are the classic pruning rules.