🗓️ Day 31: Dynamic Programming on Palindromic Substrings

🧠 Concept Deep Dive

While backtracking helps list all palindromic partitions, Dynamic Programming can efficiently determine which substrings are palindromes, saving time during repeated checks.

The goal is to fill a dp[i][j] table where:

• dp[i][j] = true if s[i..j] is a palindrome

This avoids repeated calls to isPalindrome.

🎯 Visual Intuition

For s = "ababa", we want to build:

     a  b  a  b  a
  ----------------
a | T  F  T  F  T
b |    T  F  T
a |       T  F
b |          T
a |             T

• dp[i][j] = true if:
  • s[i] === s[j] AND
  • j - i <= 2 (length 1 or 2) OR dp[i+1][j-1] === true

🛠️ Key Patterns

🧵 Fill Palindrome Table with DP

function countPalindromicSubstrings(s: string): number {
  const n = s.length;
  let count = 0;
  const dp = Array.from({ length: n }, () => Array(n).fill(false));

  for (let end = 0; end < n; end++) {
    for (let start = 0; start <= end; start++) {
      if (s[start] === s[end] && (end - start <= 2 || dp[start + 1][end - 1])) {
        dp[start][end] = true;
        count++;
      }
    }
  }

  return count;
}

📘 Example

Input: "abcba"

Output: 7

Explanation:

• Palindromes: "a", "b", "c", "b", "a", "bcb", "abcba"

🧪 Homework

1. Implement countPalindromicSubstrings(s: string): number
2. Print out the DP table for small s
3. Bonus: Return all unique palindromic substrings using this table

🧠 Big-O Cheat Sheet

• Time: O(n^2)
• Space: O(n^2) for DP table

🔮 Up Next

▶️ Day 32: Palindromic Substrings with Center Expansion