2Brute2Best
🔥0
04

Palindrome DP (DP — Strings Sub-pattern)

One string. dp[i][j] is about s[i..j], built from the shorter piece s[i+1..j−1], or computed by expanding from every centre.

Signals in the problem statement
  • ›

    "palindromic substring(s)"

  • ›

    "longest palindromic subsequence"

  • ›

    "fewest insertions to make a palindrome"

  • ›

    "fewest cuts so every piece is a palindrome"

What makes it different

Fill order is by length (or i from the end), not row by row from the top. Subsequence versions equal LCS(s, reverse(s)); substring versions don't.

Questions

ordered from “learn the idea” to “recognise it without help”
  1. 1
    Palindromic Substrings
    Basic Anchor·LeetCode #647
    Medium
  2. 2
    Longest Palindromic Substring
    Basic Reinforcement·LeetCode #5
    Medium
  3. 3
    Longest Palindromic Subsequence
    Slight Variation·LeetCode #516
    Medium
  4. 4
    Minimum Insertion Steps to Make a String Palindrome
    Pattern Transfer·LeetCode #1312
    Hard
  5. 5
    Palindrome Partitioning II
    Tricky / Edge Case·LeetCode #132
    Hard

Template

palindrome-template.cpp
// Expand around each of the 2N - 1 centres (a character, or the gap between two).
// Every successful expansion is one more palindromic substring.
int countPalindromes(const string& s, int& bestStart, int& bestLen) {
    int n = s.size(), count = 0;
    bestStart = 0; bestLen = n ? 1 : 0;
    for (int centre = 0; centre < 2 * n - 1; centre++) {
        int l = centre / 2, r = l + centre % 2;      // odd: l == r, even: r = l + 1
        while (l >= 0 && r < n && s[l] == s[r]) {
            count++;
            if (r - l + 1 > bestLen) { bestLen = r - l + 1; bestStart = l; }
            l--; r++;
        }
    }
    return count;                                    // longest = s.substr(bestStart, bestLen)
}
Remember this · DP — Strings
Trigger
Longest common subsequence, edit distance, palindromes, matching with wildcards, interleaving.
Think
Look at the last characters: if they match, what do I do? If not, what are my options?
Key question
What does dp[i][j] mean, and what are the empty-string base cases?
Common substring