132. Palindrome Partitioning II

At a Glance

• Topic: dp-1d
• Pattern: Dynamic Programming — prefix min cuts + palindrome preprocessing
• Difficulty: Hard
• Companies: Google, Amazon, Microsoft, Atlassian, Adobe
• Frequency: High
• LeetCode: 132

Problem (one-liner)

Partition string s into palindromes; return the minimum number of cuts so that every piece is a palindrome (cuts are between characters; answer can be 0 when the full string is a palindrome).

Recognition Cues

• Minimum cuts = min steps to segment — interval / prefix DP
• Palindrome checks must be O(1) after O(n^2) preprocess — expand-from-center or DP table palindrome[left][right]

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Try every partition recursively — exponential.
• cuts[end] — min cuts for prefix ending at end; inner loop tries last palindrome piece — O(n^2) after palindrome table — optimal.

Optimal Solution

Go

func minCut(word string) int {
	length := len(word)
	if length <= 1 {
		return 0
	}
	palindrome := make([][]bool, length)
	for row := range palindrome {
		palindrome[row] = make([]bool, length)
	}
	for end := 0; end < length; end++ {
		for start := end; start >= 0; start-- {
			if word[start] == word[end] && (end-start <= 2 || palindrome[start+1][end-1]) {
				palindrome[start][end] = true
			}
		}
	}
	cuts := make([]int, length)
	for end := 0; end < length; end++ {
		if palindrome[0][end] {
			cuts[end] = 0
			continue
		}
		best := length
		for start := 0; start < end; start++ {
			if palindrome[start+1][end] && cuts[start]+1 < best {
				best = cuts[start] + 1
			}
		}
		cuts[end] = best
	}
	return cuts[length-1]
}

JavaScript

function minCut(word) {
  const length = word.length;
  if (length <= 1) {
    return 0;
  }
  const palindrome = Array.from({ length }, () => Array(length).fill(false));
  for (let end = 0; end < length; end += 1) {
    palindrome[end][end] = true;
    for (let start = end; start >= 0; start -= 1) {
      if (word[start] === word[end] && (end - start <= 2 || palindrome[start + 1][end - 1])) {
        palindrome[start][end] = true;
      }
    }
  }
  const cuts = new Array(length).fill(0);
  for (let end = 0; end < length; end += 1) {
    if (palindrome[0][end]) {
      cuts[end] = 0;
      continue;
    }
    let best = length;
    for (let start = 0; start < end; start += 1) {
      if (palindrome[start + 1][end] && cuts[start] + 1 < best) {
        best = cuts[start] + 1;
      }
    }
    cuts[end] = best;
  }
  return cuts[length - 1];
}

Walkthrough

Build palindrome[start][end] expanding from centers. cuts[end] = min over splits start where [start+1..end] palindrome of cuts[start]+1. Base cuts[0]=0.

Invariant: cuts[index] minimal for prefix 0..index.

Edge Cases

• Already palindrome — 0 cuts
• All distinct chars — n-1 cuts
• Length 1 — 0

Pitfalls

• Off-by-one on inner slice [start+1..end] vs [start..end]
• Recomputing palindrome checks naively — blows time budget

Similar Problems

• 131. Palindrome Partitioning — enumerate all partitions (Medium)
• 5. Longest Palindromic Substring — palindrome structure (Medium)
• 32. Longest Valid Parentheses — substring optimization with structure (Hard)

Variants

• Return actual cuts / pieces — backtrack choices where cuts[end] transitions tie-break lexically.
• Weighted cuts — add partition penalty weights.
• k palindrome cover — NP-hard generalization; DP only for small k.

Mind-Map Tags

#palindrome-dp #prefix-dp #minimum-cuts #interval-table #o-n-squared