Eric Campbell 6 min read Engineering

Palindrome Partitioning: Minimum Cuts DP

Given a string, partition it such that every substring in the partition is a palindrome. Return the minimum number of cuts needed to achieve this. This classic dynamic programming problem appears...

Key Insights

  • The minimum palindrome partitioning problem requires two interconnected DP tables: one for O(1) palindrome lookups and another for tracking minimum cuts, reducing time complexity from exponential to O(n²).
  • Preprocessing palindrome checks into a lookup table is essential—without it, repeated substring validation dominates runtime and defeats the purpose of dynamic programming.
  • The recurrence relation minCuts[i] = min(minCuts[j-1] + 1) for all valid palindrome endings captures the optimal substructure, where each cut decision builds on previously solved subproblems.

Introduction & Problem Statement

Given a string, partition it such that every substring in the partition is a palindrome. Return the minimum number of cuts needed to achieve this. This classic dynamic programming problem appears frequently in technical interviews and has practical applications beyond algorithmic puzzles.

In text processing, palindrome partitioning helps with pattern recognition and data compression. DNA sequence analysis uses similar techniques to identify symmetric genetic patterns. Compilers use related algorithms for parsing and tokenization where symmetric structures matter.

Here’s what the problem looks like in practice:

# Input: "aab"
# Output: 1
# Explanation: ["aa", "b"] requires 1 cut

# Input: "a"
# Output: 0
# Explanation: Already a palindrome, no cuts needed

# Input: "ab"
# Output: 1
# Explanation: ["a", "b"] requires 1 cut

# Input: "aabbc"
# Output: 2
# Explanation: ["aa", "bb", "c"] requires 2 cuts

The key insight is that a string of length n requires at most n-1 cuts (splitting into individual characters), but we want the minimum. When the entire string is already a palindrome, we need zero cuts.

Brute Force Approach

The naive approach tries every possible partition point recursively. For each position, we check if the prefix is a palindrome, and if so, recursively solve for the remaining suffix.

def min_cuts_brute_force(s: str) -> int:
    def is_palindrome(string: str) -> bool:
        return string == string[::-1]
    
    def helper(string: str) -> int:
        # Base case: empty string or already palindrome
        if len(string) == 0 or is_palindrome(string):
            return 0
        
        min_cuts = len(string) - 1  # Worst case: cut every character
        
        # Try every possible first cut position
        for i in range(1, len(string)):
            if is_palindrome(string[:i]):
                # If prefix is palindrome, solve for suffix
                cuts = 1 + helper(string[i:])
                min_cuts = min(min_cuts, cuts)
        
        return min_cuts
    
    return helper(s)

This solution has exponential time complexity—O(2^n) in the worst case. Each position presents a binary choice (cut or don’t cut), and we explore all combinations. The palindrome check at each step adds O(n) overhead, making this approach impractical for strings longer than 20-25 characters.

The inefficiency stems from two sources: overlapping subproblems (we solve the same suffix multiple times) and repeated palindrome checks (we verify the same substrings repeatedly). Dynamic programming addresses both issues.

Understanding the DP Substructure

The problem exhibits optimal substructure: the minimum cuts for a string depends on the minimum cuts for its substrings. If we know the minimum cuts for all prefixes of our string, we can compute the answer for the full string by considering where to place the last cut.

Define minCuts[i] as the minimum number of cuts needed for the substring s[0..i] (inclusive). The recurrence relation is:

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

The intuition: if s[j..i] is a palindrome, we can make one cut before position j and add it to the optimal solution for s[0..j-1].

# Pseudocode for state transitions
# For string "aab" (indices 0, 1, 2):

# minCuts[0] = 0  (single char 'a' is palindrome)
# minCuts[1] = 0  (s[0..1] = "aa" is palindrome)
# minCuts[2] = ?
#   - Check if s[0..2] = "aab" is palindrome? No
#   - Check if s[1..2] = "ab" is palindrome? No
#   - Check if s[2..2] = "b" is palindrome? Yes
#     So minCuts[2] = minCuts[1] + 1 = 0 + 1 = 1

This approach reduces our problem to O(n²) subproblems, but we still need efficient palindrome checks.

Preprocessing: Palindrome Lookup Table

Checking if a substring is a palindrome in O(1) requires preprocessing. We build a 2D boolean table where isPalin[i][j] indicates whether s[i..j] is a palindrome.

The key observation: s[i..j] is a palindrome if and only if s[i] == s[j] and s[i+1..j-1] is a palindrome (or j - i < 2).

def build_palindrome_table(s: str) -> list[list[bool]]:
    n = len(s)
    # isPalin[i][j] = True if s[i:j+1] is a palindrome
    isPalin = [[False] * n for _ in range(n)]
    
    # Every single character is a palindrome
    for i in range(n):
        isPalin[i][i] = True
    
    # Check substrings of length 2
    for i in range(n - 1):
        isPalin[i][i + 1] = (s[i] == s[i + 1])
    
    # Check substrings of length 3 and above
    # We iterate by length to ensure subproblems are solved first
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # Outer characters match AND inner substring is palindrome
            isPalin[i][j] = (s[i] == s[j]) and isPalin[i + 1][j - 1]
    
    return isPalin

This preprocessing takes O(n²) time and space. Now every palindrome check is O(1), which is critical for the main DP solution’s efficiency.

Complete DP Solution

With the palindrome table ready, we implement the full bottom-up solution:

def min_cut(s: str) -> int:
    if not s or len(s) <= 1:
        return 0
    
    n = len(s)
    
    # Step 1: Build palindrome lookup table
    isPalin = [[False] * n for _ in range(n)]
    
    for i in range(n):
        isPalin[i][i] = True
    
    for i in range(n - 1):
        isPalin[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
            isPalin[i][j] = (s[i] == s[j]) and isPalin[i + 1][j - 1]
    
    # Step 2: Compute minimum cuts
    # minCuts[i] = minimum cuts for s[0..i]
    minCuts = [0] * n
    
    for i in range(n):
        if isPalin[0][i]:
            # Entire prefix is palindrome, no cuts needed
            minCuts[i] = 0
        else:
            # Worst case: cut after every character
            minCuts[i] = i
            
            # Try every possible last palindrome
            for j in range(1, i + 1):
                if isPalin[j][i]:
                    # s[j..i] is palindrome, consider cutting before j
                    minCuts[i] = min(minCuts[i], minCuts[j - 1] + 1)
    
    return minCuts[n - 1]

Let’s trace through with “aabbc”:

Palindrome table (True positions):
- Single chars: [0,0], [1,1], [2,2], [3,3], [4,4]
- Length 2: [0,1] ("aa"), [2,3] ("bb")
- Length 3+: None

minCuts computation:
- i=0: isPalin[0][0]=True → minCuts[0]=0
- i=1: isPalin[0][1]=True → minCuts[1]=0
- i=2: isPalin[0][2]=False, check j=1,2
        j=2: isPalin[2][2]=True → minCuts[1]+1=1
        minCuts[2]=1
- i=3: isPalin[0][3]=False, check j=1,2,3
        j=2: isPalin[2][3]=True → minCuts[1]+1=1
        minCuts[3]=1
- i=4: isPalin[0][4]=False, check j=1,2,3,4
        j=4: isPalin[4][4]=True → minCuts[3]+1=2
        minCuts[4]=2

Result: 2 cuts → ["aa", "bb", "c"]

Time complexity is O(n²) for both the palindrome table and the minimum cuts computation. Space complexity is O(n²) for the palindrome table plus O(n) for the cuts array.

Optimizations & Variations

We can reduce space by building the palindrome table on-the-fly while computing cuts. This approach expands around each center rather than precomputing all palindromes:

def min_cut_optimized(s: str) -> int:
    if not s or len(s) <= 1:
        return 0
    
    n = len(s)
    # minCuts[i] = minimum cuts for s[0..i-1]
    # We use i-1 indexing to simplify boundary handling
    minCuts = list(range(-1, n))  # [-1, 0, 1, 2, ..., n-1]
    
    for center in range(n):
        # Odd-length palindromes (single center)
        left, right = center, center
        while left >= 0 and right < n and s[left] == s[right]:
            # s[left..right] is a palindrome
            minCuts[right + 1] = min(minCuts[right + 1], minCuts[left] + 1)
            left -= 1
            right += 1
        
        # Even-length palindromes (two centers)
        left, right = center, center + 1
        while left >= 0 and right < n and s[left] == s[right]:
            minCuts[right + 1] = min(minCuts[right + 1], minCuts[left] + 1)
            left -= 1
            right += 1
    
    return minCuts[n]

This version uses O(n) space while maintaining O(n²) worst-case time. The key insight is that we only need to consider palindromes that actually exist in the string, not all possible substrings.

For even faster palindrome detection, Manacher’s algorithm finds all palindromic substrings in O(n) time. However, the overall complexity remains O(n²) because we still need to consider all possible cut positions.

Related problems worth exploring include counting all possible palindrome partitions (use backtracking with memoization) and finding the longest palindromic subsequence (different DP formulation).

Conclusion & Practice Problems

The minimum palindrome partitioning problem demonstrates how combining multiple DP tables solves complex optimization problems efficiently. The critical insights are recognizing the need for O(1) palindrome lookups and formulating the correct recurrence relation.

Common pitfalls include forgetting to handle the base case when the entire string is already a palindrome, off-by-one errors in index boundaries, and attempting to optimize prematurely before understanding the basic solution.

Practice these related problems to solidify your understanding:

  • LeetCode 132: Palindrome Partitioning II (this exact problem)
  • LeetCode 131: Palindrome Partitioning (return all partitions)
  • LeetCode 5: Longest Palindromic Substring
  • LeetCode 647: Palindromic Substrings (count all)

Master this pattern, and you’ll handle most substring DP problems with confidence.

Liked this? There's more.

Every week: one practical technique, explained simply, with code you can use immediately.