Lab 07 — Palindrome DP

Goal

Solve Longest Palindromic Subsequence (LC 516) and Palindrome Partitioning II (LC 132 — minimum cuts) with the four-stage progression. Internalize the length-ascending iteration that makes interval DP correct, and the is_pal[i][j] precompute that powers most palindrome problems. After this lab you can solve any palindrome-DP variant in <12 minutes.

Background Concepts

Palindrome DP problems split into two families:

  1. Subsequence palindromes (LC 516): dp[i][j] = length of longest palindromic subsequence of s[i..j]. Recurrence: if s[i] == s[j], dp[i][j] = 2 + dp[i+1][j-1]; else dp[i][j] = max(dp[i+1][j], dp[i][j-1]).

  2. Substring palindromes (LC 132, LC 5, LC 647): precompute is_pal[i][j] = (s[i..j] is a palindrome) via interval DP, then layer the partitioning / counting DP on top.

The shared mechanic: iterate by length ascending, since dp[i][j] depends on intervals strictly shorter. This is the defining feature of interval DP (deeper exploration in Lab 09).

Interview Context

Longest Palindromic Subsequence is a top-30 Medium DP problem; Palindrome Partitioning II is a Hard variant asked at Google and Microsoft. The is_pal precompute is the unlock for ~10 distinct LeetCode problems (5, 131, 132, 516, 647, 1278, 1312, 1771, …). Candidates who can derive the length-ascending loop and articulate the substring-vs-subsequence distinction signal solid interval-DP fluency.

Problem Statement

LC 516 (LPS subsequence): Given a string s, return the length of the longest palindromic subsequence.

LC 132 (min cuts): Given a string s, return the minimum number of cuts needed to partition s into palindromic substrings.

Constraints

  • 1 ≤ s.length ≤ 1000 (LC 516) / 2000 (LC 132).
  • s is lowercase English.

Clarifying Questions

  1. Subsequence or substring? (Subsequence for LC 516; substring for LC 132 partitioning.)
  2. Is a single character a palindrome? (Yes — length 1.)
  3. Is the empty string a palindrome? (Conventionally yes.)
  4. LC 132: must each part be non-empty? (Yes.)
  5. LC 132: 0 cuts means the entire string is a palindrome.

Examples

LC 516:
"bbbab"               → 4   ("bbbb")
"cbbd"                → 2   ("bb")
"a"                   → 1

LC 132:
"aab"                 → 1   ("aa" | "b")
"a"                   → 0
"ab"                  → 1
"aabb"                → 1   ("aa" | "bb")
"abcbm"               → 2
"abc"                 → 2

Initial Brute Force (LC 516)

def lps_brute(s):
    def f(i, j):
        if i > j: return 0
        if i == j: return 1
        if s[i] == s[j]: return 2 + f(i+1, j-1)
        return max(f(i+1, j), f(i, j-1))
    return f(0, len(s) - 1)

Brute Force Complexity

O(2^N) worst case — every mismatch branches. At N=1000, infeasible.

Optimization Path

(i, j) has only O(N²) distinct values, so memoization is O(N²) time and space. Tabulation: iterate length = 1..N, then i = 0..N-length, then derive j = i + length - 1. The length-ascending order ensures all shorter intervals are computed first.

LC 132 strategy: precompute is_pal[i][j] in O(N²). Then cuts[i] = min cuts for s[:i+1]; cuts[i] = -1 if s[:i+1] is itself a palindrome; else cuts[i] = min(cuts[j-1] + 1 : 0 ≤ j ≤ i, s[j..i] palindrome).

Final Expected Approach

LC 516:

dp[i][j] = LPS of s[i..j]
dp[i][i] = 1; dp[i][j] = 0 for i > j
For length 2..N:
    For i in 0..N-length:
        j = i + length - 1
        if s[i] == s[j]:
            dp[i][j] = (2 if length == 2 else 2 + dp[i+1][j-1])
        else:
            dp[i][j] = max(dp[i+1][j], dp[i][j-1])
Answer: dp[0][N-1]

LC 132:

1. Compute is_pal[i][j] (O(N^2)).
2. cuts[i] = min cuts to partition s[0..i].
   cuts[i] = 0 if is_pal[0][i].
   else cuts[i] = min(cuts[j-1] + 1 : 1 <= j <= i, is_pal[j][i]).
Answer: cuts[N-1].

Data Structures Used

  • 2D dp[N][N] (LC 516).
  • 2D is_pal[N][N] boolean + 1D cuts[N] (LC 132).

Correctness Argument

LC 516: by induction on length. Base: length 1 → 1. Inductive: an LPS of s[i..j] either uses both endpoints (must be equal, contributing 2 + LPS of s[i+1..j-1]) or skips at least one endpoint (LPS of s[i+1..j] or s[i..j-1]). The max covers all cases.

LC 132: every valid partition has a last cut at some position j, splitting into s[0..j-1] + s[j..i] where s[j..i] is a palindrome. The minimum is over all valid j. This exhausts all partitions.

Complexity

ProblemTimeSpace
LC 516 bruteO(2^N)O(N)
LC 516 memoO(N²)O(N²)
LC 516 tabO(N²)O(N²)
LC 516 space-optO(N²)O(N)
LC 132O(N²)O(N²)

Implementation Requirements

# ==== LC 516: Longest Palindromic Subsequence ====

# ---- Stage 1: Brute force ----
def lps_brute(s):
    def f(i, j):
        if i > j: return 0
        if i == j: return 1
        if s[i] == s[j]: return 2 + f(i+1, j-1)
        return max(f(i+1, j), f(i, j-1))
    return f(0, len(s) - 1)

# ---- Stage 2: Memoized ----
from functools import lru_cache
def lps_memo(s):
    @lru_cache(None)
    def f(i, j):
        if i > j: return 0
        if i == j: return 1
        if s[i] == s[j]: return 2 + f(i+1, j-1)
        return max(f(i+1, j), f(i, j-1))
    return f(0, len(s) - 1)

# ---- Stage 3: Tabulated 2D ----
def lps_tab(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n): dp[i][i] = 1
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = 2 if length == 2 else 2 + dp[i+1][j-1]
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]

# ---- Stage 4: Space-optimized 1D ----
def longestPalindromeSubseq(s):
    n = len(s)
    dp = [0] * n
    for i in range(n - 1, -1, -1):
        new = [0] * n
        new[i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                new[j] = 2 + (dp[j-1] if j-1 >= i+1 else 0)
            else:
                new[j] = max(dp[j], new[j-1])
        dp = new
    return dp[n-1]

# ==== LC 132: Palindrome Partitioning II ====

def minCut(s):
    n = len(s)
    # Step 1: precompute is_pal in O(N^2)
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n): is_pal[i][i] = True
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and (length == 2 or is_pal[i+1][j-1]):
                is_pal[i][j] = True
    # Step 2: cuts DP
    cuts = [0] * n
    for i in range(n):
        if is_pal[0][i]:
            cuts[i] = 0
            continue
        cuts[i] = i  # worst case: cut after every character
        for j in range(1, i + 1):
            if is_pal[j][i]:
                cuts[i] = min(cuts[i], cuts[j-1] + 1)
    return cuts[n-1]

Tests

  • LC 516: "bbbab" → 4. "cbbd" → 2. "a" → 1. "ac" → 1. "aaaa" → 4.
  • LC 132: "aab" → 1. "a" → 0. "ab" → 1. "aabb" → 1. "abcbm" → 2. "abacabaca" → 0 (already a palindrome? no: check) → actually "abacaba" is, but "abacabaca" is not — answer 1.
  • Cross-implementation check on random N≤10.

Follow-up Questions

  1. “Count palindromic substrings.” (LC 647) → Sum is_pal[i][j] over all (i, j) with i ≤ j.
  2. “Longest palindromic substring.” (LC 5) → Return the length / actual string of the largest (j - i + 1) with is_pal[i][j].
  3. “Minimum insertions to make palindrome.” (LC 1312) → len(s) - LPS(s).
  4. “All palindrome partitions.” (LC 131) → Backtracking; output exponentially many.
  5. “Palindromes with one allowed mismatch.” → Add a dimension dp[i][j][k] where k ∈ {0, 1}.

Product Extension

Palindrome detection appears in DNA-sequence analysis (palindromic motifs are biologically meaningful: restriction sites, hairpins), text-search systems, and as a non-trivial benchmark for compiler optimization. The is_pal precompute is also useful in interview problems that don’t strictly need DP (just O(N²) precomputation).

Language/Runtime Follow-ups

  • Python: 2D arrays via list comprehensions; lru_cache for memoization.
  • Java: boolean[][] isPal = new boolean[n][n]; defaults to false. int[][] dp = new int[n][n];.
  • Go: pre-allocate slice-of-slices; can fuse is_pal and cuts computation in a single function.
  • C++: vector<vector<bool>> is_pal(n, vector<bool>(n, false));.
  • JS/TS: as Python; watch for shared-reference trap.

Common Bugs

  1. Iterating i, j in row-major for LPS — fails because dp[i][j] depends on dp[i+1][j-1], which hasn’t been computed yet. Must iterate by length.
  2. Forgetting dp[i][i] = 1 — base case for single-char palindromes.
  3. Edge case length == 2 — dp[i+1][j-1] is dp[i+1][i], an invalid range. Special-case to 0 or just use 2.
  4. LC 132: forgetting the is_pal[0][i] short-circuit — gives wrong answer for already-palindromic input.
  5. LC 132: cuts initialization — initialize to i (worst case: cut after every character of s[0..i]).
  6. Confusing subsequence and substring — LC 516 wants subsequence; many candidates accidentally solve substring (which is LC 5, harder).

Debugging Strategy

For LC 516 "bbbab": trace the table by length. Length 1: diagonal all 1. Length 2: dp[0][1]=2 (bb), dp[1][2]=2, dp[2][3]=1, dp[3][4]=1. Length 3: dp[0][2]=3 (bbb). Length 4: dp[0][3]=3, dp[1][4]=3. Length 5: dp[0][4]=4 (bbbb). For LC 132 "aab": is_pal = [[T,T,F],[F,T,F],[F,F,T]]; cuts = [0, 0, 1].

Mastery Criteria

  • Recognized “longest palindromic subsequence” as interval DP within 60 seconds.
  • Articulated the length-ascending iteration order in <30 seconds.
  • Wrote LC 516 brute recursion in <2 minutes.
  • Wrote LC 516 tabulated in <5 minutes.
  • Wrote is_pal precompute correctly in <4 minutes.
  • Wrote LC 132 cuts DP using is_pal in <5 minutes.
  • Stated O(N²) time and space.
  • Solved LC 516 unaided in <12 minutes (full progression).
  • Solved LC 132 unaided in <15 minutes.
  • Solved LC 5 (longest palindromic substring) in <8 minutes via is_pal.