Palindrome Partitioning, in depth: minimum cuts from the recurrence to O(n) memory, reconstruction, enumeration and testing

The problem and its two variants

Given a string s of length n, a partition is a sequence of non-empty substrings whose concatenation is s. It is palindromic if every piece is a palindrome. A partition into k pieces uses k − 1 cuts. Two questions are usually asked:

• Minimum cuts (LeetCode 132): the smallest number of cuts for a palindromic partition. Every single character is a palindrome, so n − 1 cuts always work, and the answer is 0 exactly when s is itself a palindrome.
• All partitions (LeetCode 131): list every palindromic partition. The output can be exponential in size, so this is a backtracking problem that only uses DP to speed up its palindrome checks.

Why greedy fails

The tempting shortcut is to take the longest palindromic prefix, cut, and repeat. It fails on a four-letter string. For aaba, the longest palindromic prefix is aa (neither aab nor aaba is a palindrome). That leaves ba, which needs one more cut: aa|b|a, 2 cuts. The optimum is a|aba, 1 cut. Taking a shorter first piece left a longer palindrome available later.

The problem also has the property that makes DP work. If the last piece of an optimal partition is s[j..i], then the partition of the prefix s[0..j-1] must itself be optimal, or we could swap in a better one. That is optimal substructure. Many different paths reach the same prefix, which gives overlapping subproblems. Greedy fails because a locally best choice can rule out the globally best one. DP succeeds because it keeps the best answer for every prefix and tries every possible last piece.

The recurrence from first principles

Define cut[i] as the minimum cuts for the prefix s[0..i] (inclusive). Look at the last piece s[j..i] for each j from 0 to i:

• If s[j..i] is a palindrome and j = 0, the whole prefix is one piece and costs 0 cuts.
• If s[j..i] is a palindrome and j > 0, the cost is cut[j-1] + 1: the best way to finish at j − 1, plus the cut before position j.

So cut[i] = min over palindromic s[j..i] of (j == 0 ? 0 : cut[j-1] + 1). The answer is cut[n-1]. Single characters are always palindromes, so the minimum is never empty and cut[i] <= i.

That leaves the palindrome test. Checking each s[j..i] from scratch costs O(n) per pair and O(n³) overall. The interval recurrence fixes it: s[j..i] is a palindrome if and only if s[j] == s[i] and either the span has length at most 2, or the inner span s[j+1..i-1] is a palindrome. If you store those answers in pal[j][i], each test costs O(1).

The O(n²) solution with a palindrome table

The order of evaluation is the only subtle part. pal[j][i] depends on pal[j+1][i-1], which has a larger start and a smaller end. If the outer loop runs over i (the end) in increasing order and the inner loop over j, the inner span always ends at i − 1. That row of ends was finished in the previous outer iteration, so both tables fill in a single pass:

def min_cut(s: str) -> int:
    n = len(s)
    if n <= 1:
        return 0
    pal = [[False] * n for _ in range(n)]   # pal[j][i]: s[j..i] is a palindrome
    cut = [0] * n                           # cut[i]: min cuts for s[0..i]
    for i in range(n):
        best = i                            # worst case: cut before every char
        for j in range(i + 1):
            if s[j] == s[i] and (i - j < 2 or pal[j + 1][i - 1]):
                pal[j][i] = True
                best = 0 if j == 0 else min(best, cut[j - 1] + 1)
        cut[i] = best
    return cut[n - 1]

Time is Θ(n²): the double loop does constant work per (j, i) pair. Memory is Θ(n²) for pal. At n = 2,000 that is 4 million booleans, fine in any language. At n = 10⁵ it is 10¹⁰ entries. That is about 10 GB as a packed byte array and far more as Python lists, which is why the next version matters. Do not break out of the inner loop early when best reaches 0. Every later j still has to record its pal[j][i] entry, because a later i will read it.

O(n) memory with centre expansion

Notice that cut never needs the palindrome table as a table. It only needs to visit every palindromic span once and relax the cut value at its right end. Centre expansion does exactly that. There are 2n − 1 centres (each character, and each gap between two characters). From each centre, grow outward while the ends match. Every step of the expansion finds a palindrome s[l..r], so you can relax cut[r] right away:

def min_cut_linear_space(s: str) -> int:
    n = len(s)
    # cut[k] = min cuts for the prefix of length k; cut[0] = -1 makes
    # "whole prefix is one palindrome" cost -1 + 1 = 0 without a special case.
    cut = list(range(-1, n))
    for centre in range(n):
        for l, r in ((centre, centre), (centre, centre + 1)):   # odd, even
            while l >= 0 and r < n and s[l] == s[r]:
                cut[r + 1] = min(cut[r + 1], cut[l] + 1)
                l -= 1
                r += 1
    return cut[n]

Why is it correct when centres are processed left to right? The relaxation of cut[r+1] reads cut[l], where l is at most the centre. Every palindrome ending before or at position l − 1 has a centre at or left of l − 1, so it was already processed. The value is final by the time it is read. Time is still O(n²) in the worst case: in aaaa…a every substring is a palindrome and is visited once. On typical text, though, most expansions stop after one or two steps, so it runs close to linear. Memory is O(n). The -1 sentinel shifts to 1-based prefix lengths, which removes the j = 0 branch. It is also the most common source of off-by-one bugs, so keep a brute-force test nearby.

Worked example: noonabbad

Take s = "noonabbad" (n = 9). Filling cut left to right with the quadratic version gives the values below. Two moments are worth tracing. At i = 3 the inner loop finds s[0..3] = noon with j = 0, so cut[3] drops to 0, even though cut[1] and cut[2] were 1. At i = 7 it finds s[4..7] = abba, so cut[7] = cut[3] + 1 = 1. Without that span, the best option would have been cut[6] + 1 = 3.

The answer is 2 cuts: noon|abba|d.

Reconstructing the partition

Interviews often stop at the number, but real uses (segmenting DNA reads, building test strings, explaining an answer) need the partition itself. Store the j that achieved the minimum for each i, then walk backwards from the end:

def min_cut_partition(s: str) -> list[str]:
    n = len(s)
    pal = [[False] * n for _ in range(n)]
    cut, start = [0] * n, [0] * n          # start[i]: first index of last piece
    for i in range(n):
        cut[i], start[i] = i, i
        for j in range(i + 1):
            if s[j] == s[i] and (i - j < 2 or pal[j + 1][i - 1]):
                pal[j][i] = True
                c = 0 if j == 0 else cut[j - 1] + 1
                if c < cut[i]:
                    cut[i], start[i] = c, j
    parts, i = [], n - 1
    while i >= 0:
        parts.append(s[start[i]:i + 1])
        i = start[i] - 1
    return parts[::-1]

assert min_cut_partition("noonabbad") == ["noon", "abba", "d"]
assert min_cut_partition("aaba") == ["a", "aba"]

Ties go to the first j that reaches the minimum, so the output is deterministic. If your API promises another tie-break, change the comparison and document it.

Enumerating every partition

For LeetCode 131 you return every palindromic partition. Backtracking over the start position does the job. Precompute pal so each candidate piece is tested in O(1), and the rest of the cost is output size:

def all_partitions(s: str) -> list[list[str]]:
    n = len(s)
    pal = [[False] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1):
            if s[j] == s[i] and (i - j < 2 or pal[j + 1][i - 1]):
                pal[j][i] = True
    out, path = [], []
    def go(start: int) -> None:
        if start == n:
            out.append(path.copy())
            return
        for end in range(start, n):
            if pal[start][end]:
                path.append(s[start:end + 1])
                go(end + 1)
                path.pop()
    go(0)
    return out

The output really is exponential. In a string of n identical letters every substring is a palindrome, so every one of the 2ⁿ⁻¹ ways to place cuts in the n − 1 gaps is valid. At n = 20 that is 524,288 partitions, which is why the problem caps n at 16.

Beyond quadratic time, and related variants

Quadratic time is the textbook bound, but it is not the best known. Fici, Gagie, Kärkkäinen and Kempa (2014) gave an O(n log n) algorithm for minimum palindromic factorisation. It relies on a structural fact: the palindromic suffixes of any prefix form O(log n) arithmetic progressions of lengths. The palindromic tree (eertree) of Rubinchik and Shur exposes those progressions through "series links", and the eertree-based version is the one competitive programmers usually implement. Use it when n reaches 10⁵ to 10⁶ and inputs can be adversarial. Centre expansion degrades to quadratic on strings like aaaa… or abab….

Several neighbouring problems reuse the same two-table pattern:

Failure modes

• Wrong loop order. If you fill pal with j as the outer loop running upward, pal[j+1][i-1] is read before it is written. Either run j downward from n − 1 or make the end index the outer loop, as above.
• Breaking out early. Stopping the inner loop as soon as best hits 0 leaves holes in pal that later rows depend on.
• Sentinel confusion. Mixing the 0-based cut[i] with the 1-based cut[k] in one codebase guarantees a bug. Pick one convention per function.
• Memory blow-up. An n × n table of Python booleans is about 8 bytes per entry in list pointers alone. At n = 20,000 that is roughly 3.2 GB. Switch to centre expansion or a bytearray per row long before that.
• Text is not bytes. Normalise Unicode (NFC) and decide whether you compare code points or grapheme clusters before calling anything a palindrome.

Testing it properly

The quickest way to trust any of these implementations is to compare it against a brute force that cannot be wrong, over every short string on a small alphabet. Two letters are enough to hit every structural case, and length 1 to 12 runs in seconds:

import itertools

def brute(s: str) -> int:
    n, best = len(s), len(s) - 1
    for mask in range(1 << max(n - 1, 0)):       # bit k set = cut after s[k]
        pieces, start = [], 0
        for k in range(n - 1):
            if mask >> k & 1:
                pieces.append(s[start:k + 1]); start = k + 1
        pieces.append(s[start:])
        if all(x == x[::-1] for x in pieces):
            best = min(best, bin(mask).count("1"))
    return best

for n in range(1, 13):
    for t in itertools.product("ab", repeat=n):
        s = "".join(t)
        assert min_cut(s) == brute(s) == min_cut_linear_space(s), s

On longer random strings, also check that the reconstructed pieces are palindromes, join back to s, and number exactly answer + 1.

What to do next

1. Implement min_cut from memory, then run the brute-force harness above against it.
2. Rewrite it with centre expansion and the -1 sentinel, and time both on "a" * 5000 and on random text to see the best and worst cases.
3. Add reconstruction and decide, in writing, which tie-break your API promises.
4. Solve LeetCode 131, 1278 and 1745 using the same pal table, so you can see the shared pattern.
5. Read about Manacher's algorithm for linear-time palindrome detection, and compare its centre-based view with the expansion here.
6. Contrast this prefix DP with the interval DP in longest palindromic subsequence and in matrix chain multiplication.
7. If DP still feels shaky, revisit the animated introduction to dynamic programming, then try regular expression matching.