Skip to main content

Pattern 9: Palindrome DP

The Symmetry Pattern: Detect, partition, or transform strings based on palindrome properties. Expand around center or use interval DP.

The Core Pattern​

THE MENTAL MODEL

Imagine checking if a word reads the same forwards and backwards:

  1. Palindromes are symmetric - same from both ends
  2. Two approaches: expand from center or interval DP
  3. For substring [i...j]: it's a palindrome if s[i] == s[j] AND [i+1...j-1] is palindrome
  4. Build from small intervals (length 1, 2) to large intervals
  5. Useful for partitioning, counting, or finding longest palindromes

This is Palindrome DP.

Pattern Recognition​

WHEN YOU SEE THIS PATTERN

Keywords: "palindrome", "symmetric", "partition", "palindromic substring"

Structure:

  • String/sequence with symmetry property
  • Need to check or count palindromes
  • Often involves interval/range state

State:

  • dp[i][j] = "is substring [i...j] a palindrome?"
  • OR dp[i] = "min cuts to partition s[0...i] into palindromes"

Transitions:

  • Check endpoints: s[i] == s[j]
  • Use smaller interval: dp[i+1][j-1]

Common Problems​

  • Longest Palindromic Substring
  • Palindromic Substrings (Count)
  • Longest Palindromic Subsequence
  • Palindrome Partitioning
  • Palindrome Partitioning II (Min Cuts)

(Example problems will be added here)