🗓️ Day 33: Longest Palindromic Substring

🧠 Concept Deep Dive

Finding the longest palindromic substring in a given string is a classic dynamic programming (DP) or center-expansion problem. Unlike counting all palindromes (Day 32), we now care about finding the one with the maximum length.

Two main approaches:

1. Expand Around Centers — like Day 32, but track the longest.
2. Dynamic Programming — build a table of palindromic substrings.

🎯 Visual Intuition

For string "babad",

• Palindromes: "b", "a", "bab", "aba", "d"
• Longest: "bab" or "aba"

We can expand around each character and find the longest one.

b a b a d
  ^^^     → aba
^^^       → bab

🛠️ Key Patterns

🔍 Expand Around Center (Preferred)

function longestPalindrome(s: string): string {
  if (s.length < 1) return "";

  let start = 0, end = 0;

  const expand = (left: number, right: number): number[] => {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    return [left + 1, right - 1];
  };

  for (let i = 0; i < s.length; i++) {
    const [l1, r1] = expand(i, i);     // odd length
    const [l2, r2] = expand(i, i + 1); // even length

    if (r1 - l1 > end - start) {
      start = l1;
      end = r1;
    }
    if (r2 - l2 > end - start) {
      start = l2;
      end = r2;
    }
  }

  return s.substring(start, end + 1);
}

📘 Example

Input: "cbbd"\ Output: "bb"

c b b d
  ^^

Input: "babad"\ Output: "bab" or "aba"

🧪 Homework

1. Write longestPalindrome(s: string) using center expansion.
2. Try implementing the DP table version (more space, less elegant).
3. Print both the result and its start & end indexes in the original string.

🧠 Big-O Cheat Sheet

• Time: O(n^2) — each center may expand up to n times
• Space: O(1) for center expansion, O(n^2) for DP table

🔮 Up Next

▶️ Day 34: Palindrome Partitioning with Backtracking