p75 — Palindrome Partitioning II

Source: LeetCode 132 · Hard · Topics: DP, String Companies (2024–2025): Amazon (medium-high), Microsoft (medium-high), Google (medium), Meta (medium) Loop position: The two-phase DP — first precompute a property (palindrome table), then run a second DP on top. Tests recognition that O(n²) is achievable by separating “palindromicity” from “min cuts” rather than re-checking palindromes during the cut DP.

1. Quick Context

Given a string s, partition it so every substring is a palindrome. Return the MINIMUM number of cuts needed.

Strategy: Two phases.

  • Phase 1 (O(n²)): is_pal[i][j] = is s[i..j] a palindrome. Fill by increasing length.
  • Phase 2 (O(n²)): cuts[i] = min cuts for s[:i+1]. For each i, try every j ≤ i where s[j..i] is a palindrome → cuts[i] = min(cuts[i], cuts[j-1] + 1). If s[:i+1] itself is a palindrome, cuts[i] = 0.

Total O(n²) time, O(n²) space (reducible).

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/palindrome-partitioning-ii/

STOP. 35-min timer.

3. Prerequisite Concepts

  • Palindromic substring DP (LC 5 / 647): is_pal[i][j] = s[i]==s[j] AND is_pal[i+1][j-1].
  • Phase separation: don’t conflate the palindrome-check with the cut-count DP.
  • “Cuts” vs “partitions”: cuts = partitions − 1.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Min cuts so every piece is a palindrome.

2. Clarify: Min CUTS, not min PIECES (off by one).

3. Examples: s="aab" → 1 (cut between “aa” and “b”). s="a" → 0. s="ab" → 1.

5. Brute force: Enumerate all 2^(n-1) cut positions; check each piece is palindrome. Exponential.

6. Target: O(n²).

7. Pattern: Two-phase DP — precompute property, then DP on top.

8. Develop: see solution.py.

9. Test: single char; all same char; already palindrome; pathological “abcd” → 3.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 The phase separation is the whole insight

Naively combining “is palindrome” and “min cuts” inside one loop costs O(n³) (palindrome check is O(n) per call). Phase-separating gives two clean O(n²) passes.

6.2 Phase 1: palindrome table, fill by length

for length in 1..n:
    for i in 0..n-length:
        j = i + length - 1
        if length == 1: is_pal[i][j] = True
        elif length == 2: is_pal[i][j] = (s[i] == s[j])
        else: is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]

Must fill by increasing length so is_pal[i+1][j-1] is already computed.

6.3 Phase 2: cuts DP

cuts[i] = min cuts for s[:i+1]
for i in 0..n-1:
    if is_pal[0][i]: cuts[i] = 0
    else:
        cuts[i] = min over j in 1..i where is_pal[j][i] of (cuts[j-1] + 1)

6.4 Expand-around-center alternative — O(n²) without table

Instead of a is_pal table, expand-around-center from each position (odd and even centers). When we discover s[l..r] is a palindrome, immediately update cuts[r] = min(cuts[r], cuts[l-1] + 1). Same O(n²) but only O(n) memory.

6.5 Manacher’s algorithm — O(n) palindrome enumeration

Manacher’s finds all palindromic substrings in O(n) by exploiting the symmetry of previously-found palindromes. Combined with the cuts DP, total time is O(n²) because the cuts DP itself is O(n²) — Manacher’s doesn’t help the overall bound here. But it’s worth mentioning for palindrome-heavy problems.

6.6 Connection to LC 5, LC 647, LC 131

  • LC 5 (longest palindromic substring) — uses the same is_pal table or expand-around-center.
  • LC 647 (count palindromic substrings) — counts True entries in the table.
  • LC 131 (palindrome partitioning, enumerate ALL) — backtracking on top of the table.

LC 132 (this one) is “min cuts” — DP on top of the table.

6.7 Why we can’t be greedy

Greedy “take longest palindrome from current position” fails: s="aabbaa" greedy might take “aabbaa” whole (1 piece, 0 cuts ✓) but greedy “aa” first leaves “bbaa” needing more cuts.

7. Anti-Pattern Analysis

  1. Conflate palindrome-check with cuts DP — O(n³), TLE for n=2000.
  2. Greedy “take longest palindrome” — fails (counterexample above).
  3. Count partitions instead of cuts — off by one.
  4. Fill is_pal in wrong order — read uninitialized is_pal[i+1][j-1].
  5. Recompute palindrome checks inside cuts loop — same O(n³) trap as #1.
  6. Backtracking — exponential, doesn’t apply for “min” (could memoize but harder than the DP).

8. Skills & Takeaways

  • Two-phase DP recognition.
  • Palindrome table fill order (by length, not by i/j).
  • Expand-around-center alternative.
  • Manacher’s algorithm awareness.

9. When to Move On

  • Solve cold in 30 min with O(n²) DP.
  • Articulate why naive is O(n³) and phase-separation fixes it.
  • Implement expand-around-center variant with O(n) extra memory.
  • Mention Manacher’s for the palindrome-finding subroutine.

10. Company Context

  • Amazon: L5/L6; “DP with preprocessing” probe.
  • Microsoft: L65; appears in cluster with LC 5, 647, 131.
  • Google: L5; tests phase-separation thinking.
  • Meta: E5; rare but discriminating.

Scorecard for strong: “Recognized two-phase O(n²), filled palindrome table by length correctly, articulated why naive is O(n³), mentioned expand-around-center / Manacher’s as alternatives.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
ApproachGreedy or exponentialDP after hintsTwo-phase O(n²) cold+ expand-around-center / Manacher’s
Table fillWrong orderAfter failingBy-length cold+ explains dependency
OptimizationNoneTwo-phase 2DO(n) memory via expand+ Manacher’s for O(n) palindrome enumeration
Cuts vs partitionsWrongAfter failing testCorrect cold+ cites LC 131 (enum) and LC 1278 (DP cuts II) family

12. Level Delta

  • Mid (L4): Two-phase 2D DP after one hint; correct on most tests.
  • Senior (L5): Cold two-phase O(n²) + correct fill order + articulates O(n³) trap.
  • Staff (L6): + expand-around-center for O(n) memory + Manacher’s mention + LC 131/647/5 family.
  • Principal (L7+): + suffix automaton / palindromic tree (Eertree) for advanced palindrome problems + production string-processing library design.

13. Follow-up Q&A

Q1: Return the actual partition, not just the cut count. A1: Track parent pointer in cuts DP; backtrack from cuts[n-1] to reconstruct cut positions.

Q2: What if we want max cuts (max partitions)? A2: Trivially n cuts (every char is a length-1 palindrome). Boring.

Q3: K palindromic partitions (LC 1278)? A3: Add a dimension: dp[i][k] = min changes to partition s[:i] into k palindromes (note: that variant allows char changes; different objective).

Q4: O(n log n) or better? A4: Not known. O(n²) appears tight without exploiting input structure.

Q5: Manacher’s — when does it actually help? A5: When you need to enumerate ALL palindromic substrings in O(n) total. For LC 132 it doesn’t change the overall bound (the cuts DP is O(n²)), but it does cut the palindrome-precomputation phase from O(n²) to O(n).

14. Solution Walkthrough

See solution.py:

  • min_cut_dp — two-phase O(n²) with is_pal table.
  • min_cut_expand — expand-around-center, O(n) extra memory.
  • min_cut_brute — enumerate all 2^(n-1) partitions (oracle).

15. Beyond the Problem

Principal code review: “Palindrome Partitioning II is the cleanest illustration of DP staging: precompute a property in one pass, then run a second DP on top. This pattern recurs everywhere — precompute prefix sums then range queries, precompute suffix array then string queries, precompute reachability then shortest paths. The naive O(n³) trap (recomputing palindromes inside the cuts loop) is what separates engineers who think ‘one DP per problem’ from those who think ‘pipeline of DPs.’ At the Principal bar, articulate the generalization: when an inner DP has a frequently-queried property as part of its recurrence, hoist the property into a precomputed table — Strassen’s matrix-mult, FFT-accelerated convolutions, suffix-tree-based string algorithms, and even modern compilers’ dataflow analyses all use this staging principle.”