Palindrome Partitioning

Given a string like "aab", find every way to split it so that each piece is a palindrome. This is the Palindrome Partitioning problem, and it sits at the intersection of two fundamental ideas: backtracking to enumerate all valid splits, and dynamic programming to optimize palindrome checking or to answer a different question entirely: the minimum number of cuts needed.

The Backtracking Approach

For LeetCode 131, the key observation is that a partition is built left to right. You stand at position i in the string and ask: which prefixes starting at i are themselves palindromes? For each palindrome prefix s[i..j], you commit to it as the next piece of the partition, then recurse from position j+1. When i reaches the end of the string, whatever pieces you have collected form a valid partition.

This is a classic backtracking structure. At each level of the recursion tree, you branch over every possible palindrome prefix from the current position. You push a piece onto the path going down, and pop it off coming back up.

Walking Through "aab"

Let us trace the recursion on "aab".

We start at position 0. The substrings starting at 0 are "a", "aa", and "aab". Of these, "a" is a palindrome and "aa" is a palindrome, but "aab" is not.

Branch 1: take "a" from position 0. We recurse from position 1. The substrings starting at 1 are "a" and "ab". Only "a" is a palindrome. We take "a" and recurse from position 2. The only substring starting at 2 is "b", which is a palindrome. We take "b" and recurse from position 3, which is the end of the string, so we record the partition ["a", "a", "b"].

Backtracking from position 2, there are no more options. Backtracking from position 1, "ab" is not a palindrome, so that branch is pruned.

Branch 2: take "aa" from position 0. We recurse from position 2. The only substring is "b", a palindrome. We take it and reach the end, recording ["aa", "b"].

The final answer is [["a", "a", "b"], ["aa", "b"]].

Code: Palindrome Partitioning

def partition(s):
    res = []

    def bt(start, path):
        if start == len(s):
            res.append(path[:])
            return
        for end in range(start + 1, len(s) + 1):
            sub = s[start:end]
            if sub == sub[::-1]:
                path.append(sub)
                bt(end, path)
                path.pop()

    bt(0, [])
    return res

At each recursive call, we try every possible endpoint for the next piece. We check whether the substring is a palindrome by comparing it to its reverse. If it is, we add it to the current path and recurse. On return, we pop the piece off to restore state for the next branch.

Precomputing a Palindrome Table

In the backtracking code above, every palindrome check costs $O(n)$ because we reverse the substring. Over the entire recursion tree, these checks add up. We can eliminate this cost by precomputing a table dp[i][j] that tells us in $O(1)$ whether s[i..j] is a palindrome.

The table is built from two base cases. Every single character is a palindrome: dp[i][i] = True. Every pair of adjacent characters is a palindrome if and only if they are equal: dp[i][i+1] = (s[i] == s[i+1]). For longer substrings, s[i..j] is a palindrome if and only if s[i] == s[j] and the inner substring s[i+1..j-1] is also a palindrome.

We fill the table by increasing substring length:

def build_palindrome_table(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = True

    for i in range(n - 1):
        dp[i][i + 1] = (s[i] == s[i + 1])

    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

    return dp

With this table in hand, the backtracking code replaces sub == sub[::-1] with dp[start][end - 1], making each check $O(1)$. The table itself takes $O(n^2)$ time and space to build, which is dominated by the exponential cost of enumerating all partitions.

Palindrome Partitioning II: Minimum Cuts

LeetCode 132 asks a natural follow-up question: what is the minimum number of cuts needed so that every piece is a palindrome? For "aab", one cut between "aa" and "b" suffices, so the answer is 1.

You might think of reusing the backtracking approach: enumerate all partitions and take the one with the fewest pieces. But this is disastrously slow. The number of valid partitions can be exponential (consider a string of all identical characters like "aaaa"), and we do not need to enumerate them all just to find the shortest one. This is an optimization problem, not an enumeration problem, and it calls for dynamic programming.

The DP Approach for Minimum Cuts

Define cuts[i] as the minimum number of cuts needed to partition s[0..i] into palindromes. Our goal is cuts[n-1].

The base case: if s[0..i] is itself a palindrome, then cuts[i] = 0, no cuts needed at all.

Otherwise, we try every possible position j for the last cut. If s[j..i] is a palindrome, then we could cut just before position j, giving us cuts[j-1] + 1 total cuts (the cuts[j-1] cuts needed for the prefix, plus one more cut to separate the palindrome suffix). We take the minimum over all such j:

cuts[i] = min(cuts[j-1] + 1) for all j where s[j..i] is a palindrome

We initialize cuts[i] = i as a worst case: cutting between every character gives at most i cuts for a substring of length i+1.

Walking Through "aab" with the DP

We precompute the palindrome table: dp[0][0] = True ("a"), dp[1][1] = True ("a"), dp[2][2] = True ("b"), dp[0][1] = True ("aa"), dp[1][2] = False ("ab"), dp[0][2] = False ("aab").

cuts[0]: The substring is "a". It is a palindrome, so cuts[0] = 0.

cuts[1]: The substring is "aa". It is a palindrome (dp[0][1] = True), so cuts[1] = 0.

cuts[2]: The substring is "aab". It is not a palindrome. We try each possible last cut:

• j = 0: is s[0..2] = "aab" a palindrome? No.
• j = 1: is s[1..2] = "ab" a palindrome? No.
• j = 2: is s[2..2] = "b" a palindrome? Yes. So cuts[2] = cuts[1] + 1 = 0 + 1 = 1.

The minimum number of cuts is 1, which matches our intuition: cut between "aa" and "b".

Code: Minimum Cuts

def min_cut(s):
    n = len(s)
    dp = build_palindrome_table(s)

    cuts = list(range(n))  # worst case: cuts[i] = i

    for i in range(n):
        if dp[0][i]:
            cuts[i] = 0
            continue
        for j in range(1, i + 1):
            if dp[j][i]:
                cuts[i] = min(cuts[i], cuts[j - 1] + 1)

    return cuts[n - 1]

The cuts array is initialized with cuts[i] = i, the maximum possible cuts. For each position i, we first check if the entire prefix is a palindrome. If not, we scan backwards for palindrome suffixes and take the best option.

Complexity Analysis

Palindrome Partitioning (all partitions): The number of valid palindrome partitions can be as large as $2^{n-1}$ in the worst case (a string of identical characters has every possible split as valid). Generating each partition takes $O(n)$ work to copy the path, so the total time is $O(n \cdot 2^n)$. The recursion stack uses $O(n)$ space, plus the space for storing results.

Palindrome Partitioning II (minimum cuts): Building the palindrome table takes $O(n^2)$ time and $O(n^2)$ space. The DP over cuts has a double loop, since for each i we scan all j from 1 to i, which is also $O(n^2)$. The total time is $O(n^2)$ and the total space is $O(n^2)$ for the palindrome table (the cuts array is only $O(n)$).

The jump from exponential to quadratic is exactly why the DP formulation matters. When you only need the count or the minimum, you almost never need to enumerate all solutions.

Recognizing this pattern

You're probably looking at palindrome partitioning when:

• You need to split a string into palindromic pieces, whether to count them, minimize cuts, or enumerate.
• The substring palindrome check is the inner loop, often precomputed as a 2D table.
• String length is small for enumeration (n ≤ 20) or moderate for the DP form (n ≤ 2000).
• Phrasing mentions "partition s such that every substring is a palindrome".

Common templates:

• DFS over prefixes: recurse on the next start index, try every palindromic prefix. Example: Palindrome Partitioning.
• DP for minimum cuts: cuts[i] = min cuts for s[:i+1]; transition over palindromic suffixes. Example: Palindrome Partitioning II.
• Precomputed palindrome table: fill is_pal[i][j] in $O(n^2)$, then O(1) checks. Example: Palindrome Partitioning IV.
• Partition into k palindromes: DP with an extra dimension for piece count. Example: Palindrome Partitioning III.