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).

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

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]

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

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

Loading diagram…

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

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