Palindrome Partitioning Min Cuts

Tags

Palindrome Partitioning Min Cuts

Category

Dynamic Programming

Difficulty

Very Hard

Problem Statement

Given a non-empty string, find the minimum number of cuts needed to partition the string such that every resulting substring is a palindrome. For example, given "noonabbad", one optimal partitioning is "noon | abba | d" requiring 2 cuts.

Intuition

A brute-force approach would try all possible partitions, which is exponential. Instead, we observe two separable subproblems: (1) quickly determining whether any substring s[i..j] is a palindrome, and (2) finding the minimum cuts for the prefix s[0..i]. Precomputing a palindrome lookup table in O(n^2) and then using a 1D DP for cuts yields an efficient solution. The cuts DP leverages the fact that if s[j..i] is a palindrome, then cuts[i] = min(cuts[i], cuts[j-1] + 1).

Approach

  1. Build palindrome table: Create a 2D boolean table isPalin[i][j] indicating whether s[i..j] is a palindrome. Fill it using the standard expand-from-center or bottom-up DP technique:
    • All single characters are palindromes: isPalin[i][i] = true.
    • For length 2: isPalin[i][i+1] = (s[i] == s[i+1]).
    • For length > 2: isPalin[i][j] = (s[i] == s[j]) and isPalin[i+1][j-1].
  2. Compute min cuts DP: Create an array cuts[0..n-1] where cuts[i] is the minimum number of cuts for s[0..i].
    • If isPalin[0][i] is true, then cuts[i] = 0 (the whole prefix is a palindrome, no cut needed).
    • Otherwise, initialize cuts[i] = i (worst case: cut every character) and for each j from 1 to i, if isPalin[j][i] is true, then cuts[i] = min(cuts[i], cuts[j-1] + 1).
  3. Return cuts[n-1].

Pseudocode

function palindromePartitioningMinCuts(s):
    n = length(s)
    isPalin = 2D boolean array of size n x n, initialized to false

    // Build palindrome table
    for i from 0 to n-1:
        isPalin[i][i] = true
    for length from 2 to n:
        for i from 0 to n - length:
            j = i + length - 1
            if length == 2:
                isPalin[i][j] = (s[i] == s[j])
            else:
                isPalin[i][j] = (s[i] == s[j]) and isPalin[i+1][j-1]

    // Compute min cuts
    cuts = array of size n
    for i from 0 to n-1:
        if isPalin[0][i]:
            cuts[i] = 0
            continue
        cuts[i] = i  // worst case
        for j from 1 to i:
            if isPalin[j][i]:
                cuts[i] = min(cuts[i], cuts[j-1] + 1)

    return cuts[n-1]

Time & Space Complexity

  • Time: O(n^2). Building the palindrome table is O(n^2). The cuts DP is also O(n^2) in the worst case (for each index, we scan all possible left boundaries).
  • Space: O(n^2) for the palindrome lookup table. The cuts array is O(n).

Key Insights

  • Separating "is this a palindrome?" from "what is the minimum cut count?" into two distinct DPs makes the problem tractable.
  • The worst-case number of cuts for a string of length n is n-1 (every single character is its own palindrome).
  • The palindrome table can also be built using Manacher's algorithm in O(n), but the overall cuts DP remains O(n^2), so the asymptotic complexity does not improve.
  • Cuts for a prefix ending at index i depend only on cuts for shorter prefixes, giving a clean left-to-right DP.

Edge Cases

  • Single character string: Already a palindrome, 0 cuts needed.
  • Entire string is a palindrome: 0 cuts needed.
  • All characters distinct: n-1 cuts needed (every character is its own partition).
  • All characters identical: The whole string is a palindrome, 0 cuts.
  • Two characters: 0 cuts if they are the same, 1 cut if they differ.

Linked mentions