Longest Palindromic Substring

Difficulty: Medium
Topics: Two Pointers, String, Dynamic Programming
Link: https://leetcode.com/problems/longest-palindromic-substring/

Problem Description

Given a string s, return the longest palindromic substring in s.

Example 1:


Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:


Input: s = "cbbd"
Output: "bb"

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

Solution

1. Problem Deconstruction

Technical Definition:
Given a string s of length n (1 ≤ n ≤ 1000) with alphanumeric characters, identify indices (i, j) such that the substring s[i:j+1] satisfies s[i+k] = s[j-k] for all 0 ≤ k ≤ (j-i)//2, and j-i is maximized. Return any maximal substring.

Beginner Explanation:
Find the longest sequence of characters in the string that reads the same forwards and backwards. For example, in “racecar”, the whole word is a palindrome. In “babad”, “bab” or “aba” are valid answers.

Mathematical Formulation:
Let s be a string of length n. Define:

P(i, j) = True iff s[i:j+1] is a palindrome (i.e., ∀ k ∈ [0, ⌊(j-i)/2⌋], s[i+k] = s[j-k]).
Objective:

\max_{(i,j)} \{ j - i + 1 \mid 0 \leq i \leq j < n, P(i, j) = \text{True} \}

Output: s[i^\ast:j^\ast+1] achieving this maximum.

Constraint Analysis:

1 <= s.length <= 1000:
- Solution Limitation: Permits O( $n^2$ ) algorithms (1e6 operations worst-case) but rules out O( $n^3$ ) (1e9 operations).
- Edge Case: Single-character strings are trivially palindromic.
s consists of digits/English letters:
- Solution Limitation: No Unicode handling needed; case-sensitive comparisons (e.g., ‘A’ ≠ ‘a’).
- Edge Case: All identical characters (e.g., “aaaa”) → entire string is a palindrome.

2. Intuition Scaffolding

Real-World Metaphor:
Mirror symmetry in architecture. Imagine placing mirrors at different points in a building facade; the longest symmetric wing around each mirror position is the palindrome.

Gaming Analogy:
In a side-scroller game, power-ups require symmetric sequences of tokens. Players scan for the longest symmetric token chain by expanding from centers.

Math Analogy:
Maximizing the radius $r$ of symmetry for centers $c$ (discrete points or midpoints between characters) where $s[c-r] = s[c+r]$ .

Common Pitfalls:

Ignoring even-length palindromes: Only checking odd-length (e.g., missing “bb” in “cbbd”).
Global min/max fallacy: Assuming the first/last character defines boundaries (e.g., “aab” → longest is “aa”, not from index 0).
Overlapping subproblems: Recomputing palindrome checks for substrings (solved via DP memoization).
Boundary neglect: Forgetting to terminate expansion at string start/end.
Case sensitivity oversight: Treating ‘A’ and ‘a’ as equal without specification.

3. Approach Encyclopedia

Brute Force

Pseudocode:

def longest_palindrome_brute(s):  
    n = len(s)  
    best = ""  
    for i in range(n):  
        for j in range(i, n):  
            substr = s[i:j+1]  
            if substr == substr[::-1] and len(substr) > len(best):  
                best = substr  
    return best

Complexity Proof:

Time: O( $n^3$ ) → $n^2$ substrings, each checked in O( $n$ ) via reversal.
Space: O(1) (ignoring substring storage).
Visualization:

s = "babad"  
i=0: ["b", "ba", "bab", "baba", "babad"] → "bab" valid  
i=1: ["a", "ab", "aba", "abad"] → "aba" valid  
...

Dynamic Programming

Pseudocode:

def longest_palindrome_dp(s):  
    n = len(s)  
    dp = [[False] * n for _ in range(n)]  
    start, max_len = 0, 1  # Single char is palindrome  
    # Base case 1: length=1  
    for i in range(n):  
        dp[i][i] = True  
    # Base case 2: length=2  
    for i in range(n-1):  
        if s[i] == s[i+1]:  
            dp[i][i+1] = True  
            start, max_len = i, 2  
    # Lengths > 2  
    for length in range(3, n+1):  
        for i in range(n - length + 1):  
            j = i + length - 1  
            if s[i] == s[j] and dp[i+1][j-1]:  
                dp[i][j] = True  
                start, max_len = i, length  
    return s[start:start+max_len]

Complexity Proof:

Time: O( $n^2$ ) → filling $\frac{n(n+1)}{2}$ DP cells.
Space: O( $n^2$ ) for DP table.
Visualization:

  b a b a d  
b T F T F F  
a   T F T F  
b     T F F  
a       T F  
d         T

Expand Around Center

Pseudocode:

def expand(s, left, right):  
    while left >= 0 and right < len(s) and s[left] == s[right]:  
        left -= 1  
        right += 1  
    return (left+1, right-1)  # Last valid indices  

def longest_palindrome_center(s):  
    start, end = 0, 0  
    for i in range(len(s)):  
        l1, r1 = expand(s, i, i)    # Odd-length (center at i)  
        l2, r2 = expand(s, i, i+1)  # Even-length (center between i and i+1)  
        if r1 - l1 > end - start:  
            start, end = l1, r1  
        if r2 - l2 > end - start:  
            start, end = l2, r2  
    return s[start:end+1]

Complexity Proof:

Time: O( $n^2$ ) → $2n$ centers, each expansion O( $n$ ) worst-case.
Space: O(1).
Visualization:

s = "babad", center at i=1 (char 'a'):  
Odd: expand(1,1) → (0,2) → "bab"  
Even: expand(1,2) → (1,2) → "ab" (fails)

Manacher’s Algorithm (Optimal)

Pseudocode:

def manacher(s):  
    T = '#' + '#'.join(s) + '#'  # e.g., "b" → "#b#"  
    n = len(T)  
    P = [0] * n  # Radius array  
    C = R = 0    # Center and right boundary  
    max_center = 0  
    for i in range(n):  
        mirror = 2*C - i  
        if i < R:  
            P[i] = min(R - i, P[mirror])  # Use symmetry  
        # Expand beyond mirrored radius  
        left = i - (1 + P[i])  
        right = i + (1 + P[i])  
        while left >= 0 and right < n and T[left] == T[right]:  
            P[i] += 1  
            left -= 1  
            right += 1  
        if i + P[i] > R:  
            C, R = i, i + P[i]  
        if P[i] > P[max_center]:  
            max_center = i  
    start = (max_center - P[max_center]) // 2  
    return s[start:start + P[max_center]]

Complexity Proof:

Time: O( $n$ ) → each expansion increases R (bounded by $2n$ ).
Space: O( $n$ ) for transformed string and radius array.
Visualization:

T = ^#b#a#b#a#d#$  
P = [0,1,0,3,0,3,0,1,0] → max_center=3, radius=3 → "aba"

4. Code Deep Dive

Expand Around Center Implementation:

def longestPalindrome(s):  
    if not s:  
        return ""  
    start = end = 0  # Track indices of longest palindrome  
    def expand(l, r):  
        while l >= 0 and r < len(s) and s[l] == s[r]:  
            l -= 1  
            r += 1  
        return l + 1, r - 1  # Last valid positions  
    for i in range(len(s)):  
        l_odd, r_odd = expand(i, i)   # Case 1: center at i (odd)  
        l_even, r_even = expand(i, i + 1)  # Case 2: center between i,i+1 (even)  
        # Update for odd expansion  
        if r_odd - l_odd > end - start:  
            start, end = l_odd, r_odd  
        # Update for even expansion  
        if r_even - l_even > end - start:  
            start, end = l_even, r_even  
    return s[start:end+1]

Edge Case Handling:

Example 1 (“babad”):
- At i=1 (char ‘a’):
  - Odd: expand(1,1) → (0,2) → “bab” (length=3).
  - Even: expand(1,2) → (1,2) → “ab” (invalid).
    Updates (start,end) = (0,2).
Example 2 (“cbbd”):
- At i=1 (char ‘b’):
  - Odd: expand(1,1) → (1,1).
  - Even: expand(1,2) → (1,2) → “bb” (length=2).
    Updates (start,end) = (1,2).

5. Complexity War Room

Hardware-Aware Analysis:

Expand Around Center:
- Worst-case (e.g., “aaaa”): ~ $2n \times n$ = 2000 × 1000 = 2e6 operations.
- Fits in CPU L2/L3 cache (string size < 8KB).
Manacher:
- 2000-length transformed string → 8KB RAM (fits L1 cache).

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute Force	O( $n^3$ )	O(1)	★★★★★	❌ (Fails n=1000)
Dynamic Programming	O( $n^2$ )	O( $n^2$ )	★★★★☆	✅ (n≤1000)
Expand Center	O( $n^2$ )	O(1)	★★★★☆	✅ (Optimal choice)
Manacher	O( $n$ )	O( $n$ )	★★☆☆☆	✅ (Bonus points)

6. Pro Mode Extras

Variants:

Count Palindromic Substrings (LC 647):
Modify “Expand Center” to count all expansions:

count = 0  
for center in range(len(s)):  
    count += 1  # center itself  
    count += expand(center, center+1)  # even-length

Longest Palindromic Subsequence (LC 516):
Use DP: dp[i][j] = 2 + dp[i+1][j-1] if s[i]==s[j], else max(dp[i+1][j], dp[i][j-1]).

Interview Cheat Sheet:

Key Insight: Palindromes mirror around a center → leverage symmetry.
Mention First: Time/space complexity and constraints fit.
Test Cases:
1. Single char: "a" → "a"
2. All identical: "aaa" → "aaa"
3. Even-length: "cbbd" → "bb"
4. Mixed: "babad" → "bab"
Optimization Path: Brute → DP → Expand Center → Manacher.

#5 - Longest Palindromic Substring

Longest Palindromic Substring

Problem Description

Solution

1. Problem Deconstruction

2. Intuition Scaffolding

3. Approach Encyclopedia

Brute Force

Dynamic Programming

Expand Around Center

Manacher’s Algorithm (Optimal)

4. Code Deep Dive

5. Complexity War Room

6. Pro Mode Extras