Longest Palindromic Substring - The Three Approaches

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

Example: s = "babad" → "bab" or "aba"

Understanding the Problem

A palindrome reads the same forwards and backwards:

"a" is a palindrome
"aba" is a palindrome
"abba" is a palindrome
"abc" is NOT a palindrome

We need to find the longest such substring in the given string.

1. Pure Recursion with Expand from Center (O(n²))

The Intuition

Key Insight: Every palindrome has a center. We can check each possible center and expand outward while characters match.

Two types of centers:

Odd length palindromes: Single character center (e.g., "aba")
Even length palindromes: Two character center (e.g., "abba")

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";

    int start = 0, end = 0;

    // Try each position as potential center
    for (int i = 0; i < s.length(); i++) {
        // Odd length palindromes (single center)
        int len1 = expandAroundCenter(s, i, i);
        // Even length palindromes (double center)
        int len2 = expandAroundCenter(s, i, i + 1);

        int maxLen = Math.max(len1, len2);

        // Update result if we found a longer palindrome
        if (maxLen > end - start) {
            start = i - (maxLen - 1) / 2;
            end = i + maxLen / 2;
        }
    }

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

// Expand from center and return length of palindrome
private int expandAroundCenter(String s, int left, int right) {
    // Base case: invalid indices
    if (left < 0 || right >= s.length()) return 0;

    // Expand while characters match
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }

    // Return length of palindrome
    // right - left - 1 because we've expanded one step too far
    return right - left - 1;
}

What Happens with `s = "babad"`:

Try center at 0 ('b'):
  - Odd:  "b" → length 1
  - Even: "ba" not palindrome → length 0

Try center at 1 ('a'):
  - Odd:  "bab" → length 3 ✓
  - Even: "ab" not palindrome → length 0

Try center at 2 ('b'):
  - Odd:  "aba" → length 3 ✓
  - Even: "ba" not palindrome → length 0

Try center at 3 ('a'):
  - Odd:  "a" → length 1
  - Even: "ad" not palindrome → length 0

Try center at 4 ('d'):
  - Odd:  "d" → length 1
  - Even: out of bounds → length 0

Result: "bab" (or "aba")

Complexity:

Time: O(n²) - n centers × O(n) expansion per center
Space: O(1) - only storing start/end indices

Visualization:

For "babad":

Center at index 1 ('a'):
    b a b a d
      ↑ ↑ ↑
      match! continue expanding
    ← a →
    b   b
    match! palindrome "bab"

Length = 3

2. Top-Down DP (Memoization - O(n²))

The Intuition

Key Insight: A string s[i...j] is a palindrome if:

First and last characters match: s[i] == s[j]
Inner substring is also a palindrome: s[i+1...j-1] is palindrome

We can recursively check this with memoization to avoid recomputation.

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";

    int n = s.length();
    Boolean[][] memo = new Boolean[n][n];

    int maxLen = 1;
    int start = 0;

    // Try all possible substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (isPalindrome(s, i, j, memo)) {
                int len = j - i + 1;
                if (len > maxLen) {
                    maxLen = len;
                    start = i;
                }
            }
        }
    }

    return s.substring(start, start + maxLen);
}

// Check if s[i...j] is palindrome with memoization
private boolean isPalindrome(String s, int i, int j, Boolean[][] memo) {
    // Base case: single character or empty
    if (i >= j) return true;

    // Check memo
    if (memo[i][j] != null) return memo[i][j];

    // Calculate and store result
    boolean result = false;
    if (s.charAt(i) == s.charAt(j)) {
        result = isPalindrome(s, i + 1, j - 1, memo);
    }

    memo[i][j] = result;
    return result;
}

What Happens with `s = "babad"`:

Check "babad" [0,4]:
  - s[0] != s[4] ('b' != 'd') → false, memo[0][4] = false

Check "bab" [0,2]:
  - s[0] == s[2] ('b' == 'b') ✓
  - Check inner "a" [1,1] → true (base case)
  - memo[0][2] = true ✓

Check "aba" [1,3]:
  - s[1] == s[3] ('a' == 'a') ✓
  - Check inner "b" [2,2] → true (base case)
  - memo[1][3] = true ✓

Check "abad" [1,4]:
  - s[1] != s[4] ('a' != 'd') → false, memo[1][4] = false

Longest palindrome found: "bab" or "aba" (both length 3)

Memoization Table:

For "babad":

memo[i][j]:
     0    1    2    3    4
0 [ T    F    T    F    F ]  ("b", "ba", "bab", "baba", "babad")
1 [      T    F    T    F ]  ("a", "ab", "aba", "abad")
2 [           T    F    F ]  ("b", "ba", "bad")
3 [                T    F ]  ("a", "ad")
4 [                     T ]  ("d")

T = true (palindrome)
F = false (not palindrome)

Complexity:

Time: O(n²) - each cell computed once
Space: O(n²) - memo table + O(n) recursion stack

3. Bottom-Up DP (Tabulation - O(n²))

The Intuition

Key Insight: Build solutions from smallest substrings to largest.

Build order:

Length 1: All single characters are palindromes
Length 2: Check if both characters match
Length 3+: Use previously computed results

State: dp[i][j] = true if substring s[i...j] is a palindrome

Transition:

dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i+1][j-1])

public String longestPalindrome(String s) {
    int n = s.length();
    if (n < 2) return s;

    boolean[][] dp = new boolean[n][n];
    int start = 0, maxLen = 1;

    // Base case: every single character is a palindrome
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }

    // Build by increasing length
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;

            if (s.charAt(i) == s.charAt(j)) {
                // If length is 2 or inner substring is palindrome
                if (len == 2 || dp[i+1][j-1]) {
                    dp[i][j] = true;
                    start = i;
                    maxLen = len;
                }
            }
        }
    }

    return s.substring(start, start + maxLen);
}

What Happens with `s = "babad"`:

Step 1: Initialize single characters (length 1)
dp[0][0] = true  // "b"
dp[1][1] = true  // "a"
dp[2][2] = true  // "b"
dp[3][3] = true  // "a"
dp[4][4] = true  // "d"

Step 2: Check length 2
dp[0][1] = (s[0]==s[1]) && true = false  // "ba"
dp[1][2] = (s[1]==s[2]) && true = false  // "ab"
dp[2][3] = (s[2]==s[3]) && true = false  // "ba"
dp[3][4] = (s[3]==s[4]) && true = false  // "ad"

Step 3: Check length 3
dp[0][2] = (s[0]==s[2]) && dp[1][1] = true && true = TRUE ✓  // "bab"
dp[1][3] = (s[1]==s[3]) && dp[2][2] = true && true = TRUE ✓  // "aba"
dp[2][4] = (s[2]==s[4]) && dp[3][3] = false  // "bad"

Step 4: Check length 4
dp[0][3] = (s[0]==s[3]) && dp[1][2] = false  // "baba"
dp[1][4] = (s[1]==s[4]) && dp[2][3] = false  // "abad"

Step 5: Check length 5
dp[0][4] = (s[0]==s[4]) && dp[1][3] = false  // "babad"

Result: start=0, maxLen=3 → "bab"

DP Table Evolution:

Length 1 (single characters):
  1    2    3    4
[ T    -    -    -    - ]
[      T    -    -    - ]
[           T    -    - ]
[                T    - ]
[                     T ]

Length 2 (pairs):
  1    2    3    4
[ T    F    -    -    - ]
[      T    F    -    - ]
[           T    F    - ]
[                T    F ]
[                     T ]

Length 3 (triplets):
  1    2    3    4
[ T    F    T    -    - ]  ← "bab" found!
[      T    F    T    - ]  ← "aba" found!
[           T    F    F ]
[                T    F ]
[                     T ]

Final table:
  1    2    3    4
[ T    F    T    F    F ]
[      T    F    T    F ]
[           T    F    F ]
[                T    F ]
[                     T ]

Complexity:

Time: O(n²) - two nested loops
Space: O(n²) - dp table only (no recursion stack)

Quick Comparison

Feature	Expand from Center	Memoization	Tabulation
Structure	Iterative + expand	Recursive + cache	Loop + array
Direction	Expand outward	Top-down	Bottom-up
Time	O(n²)	O(n²)	O(n²)
Space	O(1)	O(n²) memo + O(n) stack	O(n²) array only
Intuition	"Try each center"	"Is [i,j] palindrome?"	"Build small → large"
When to use	Space-efficient	Natural recursion	Classic DP pattern

The Evolution

Approach 1 → Approach 2:

// Instead of expanding, use recursion with memoization
isPalindrome(i, j):
    if memo[i][j] != null: return memo[i][j]
    result = (s[i] == s[j]) && isPalindrome(i+1, j-1)
    memo[i][j] = result
    return result

Approach 2 → Approach 3:

// Replace recursion with nested loops
for len = 2 to n:
    for i = 0 to n-len:
        j = i + len - 1
        dp[i][j] = (s[i] == s[j]) && (len <= 2 || dp[i+1][j-1])

Mental Models

Expand from Center: "A palindrome is symmetric. Let me check every possible center point and see how far I can expand while maintaining symmetry."

Memoization: "To know if [i,j] is a palindrome, I need to check if ends match and if [i+1,j-1] is a palindrome. Let me cache results so I don't recompute."

Tabulation: "Let me solve all small palindromes first (length 1, 2), then use them to build bigger palindromes (length 3, 4, ...). This way, when I need [i+1,j-1], it's already computed."

Which Approach to Use?

Use Expand from Center when:

✅ You need O(1) space
✅ You want a simple, intuitive solution
✅ String is not too large (< 10,000 characters)

Use Memoization when:

✅ You want to think recursively
✅ You need to query multiple ranges for palindrome checks
✅ The recursive structure helps you understand the problem

Use Tabulation when:

✅ You want the classic DP pattern for interval problems
✅ You're learning interval DP techniques
✅ You want to avoid recursion overhead
✅ You need to extend to related problems (like counting palindromes)

Complete Working Example

public class LongestPalindromicSubstring {

    // Approach 1: Expand from Center
    public String longestPalindromeExpand(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;

        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int maxLen = Math.max(len1, len2);

            if (maxLen > end - start) {
                start = i - (maxLen - 1) / 2;
                end = i + maxLen / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    // Approach 2: Memoization
    public String longestPalindromeMemo(String s) {
        if (s == null || s.length() < 1) return "";
        int n = s.length();
        Boolean[][] memo = new Boolean[n][n];
        int maxLen = 1, start = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isPalindrome(s, i, j, memo)) {
                    int len = j - i + 1;
                    if (len > maxLen) {
                        maxLen = len;
                        start = i;
                    }
                }
            }
        }
        return s.substring(start, start + maxLen);
    }

    private boolean isPalindrome(String s, int i, int j, Boolean[][] memo) {
        if (i >= j) return true;
        if (memo[i][j] != null) return memo[i][j];

        boolean result = false;
        if (s.charAt(i) == s.charAt(j)) {
            result = isPalindrome(s, i + 1, j - 1, memo);
        }
        memo[i][j] = result;
        return result;
    }

    // Approach 3: Tabulation
    public String longestPalindromeDP(String s) {
        int n = s.length();
        if (n < 2) return s;

        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLen = 1;

        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    if (len == 2 || dp[i+1][j-1]) {
                        dp[i][j] = true;
                        start = i;
                        maxLen = len;
                    }
                }
            }
        }
        return s.substring(start, start + maxLen);
    }

    public static void main(String[] args) {
        LongestPalindromicSubstring lps = new LongestPalindromicSubstring();
        String s = "babad";

        System.out.println("Expand from Center: " + lps.longestPalindromeExpand(s)); // "bab" or "aba"
        System.out.println("Memoization: " + lps.longestPalindromeMemo(s));           // "bab" or "aba"
        System.out.println("Tabulation: " + lps.longestPalindromeDP(s));              // "bab" or "aba"
    }
}

Common Pitfalls

Pitfall 1: Off-by-one errors in expand approach

// WRONG
int len = right - left;  // Should be right - left - 1

// RIGHT
int len = right - left - 1;  // We've expanded one step too far

Pitfall 2: Not handling even-length palindromes

// WRONG - only checks odd-length palindromes
expandAroundCenter(s, i, i);

// RIGHT - check both odd and even
expandAroundCenter(s, i, i);      // odd: "aba"
expandAroundCenter(s, i, i + 1);  // even: "abba"

Pitfall 3: Wrong base case in DP

// WRONG
if (len == 2) dp[i][j] = true;  // Forgetting to check if chars match

// RIGHT
if (s.charAt(i) == s.charAt(j)) {
    if (len == 2 || dp[i+1][j-1]) {
        dp[i][j] = true;
    }
}

Practice Extensions

Once you master these three approaches, try:

Palindromic Substrings (LC 647): Count all palindromic substrings
Longest Palindromic Subsequence (LC 516): Allow non-contiguous characters
Palindrome Partitioning (LC 131): Partition string into palindromic substrings
Minimum Insertion to Make Palindrome (LC 1312): Modify string to make it palindrome

Key Takeaways

THE PROGRESSION

Expand from Center: Natural, space-efficient, easy to understand

Think: "Check each center point"
Best for: Interviews when space matters

Memoization: Recursive thinking with caching

Think: "Is [i,j] palindrome? Cache it!"
Best for: Understanding the recursive structure

Tabulation: Classic interval DP pattern

Think: "Build small → large systematically"
Best for: Learning DP patterns, extending to other problems

All three are O(n²) time, but differ in space and style!

The Big Picture

Longest Palindromic Substring is a foundational interval DP problem.

Master it, and you'll understand:

Palindrome properties
Interval building strategies
Space-time tradeoffs
Multiple solution paradigms for the same problem

This is your palindrome foundation. Build it strong.

Understanding the Problem​

1. Pure Recursion with Expand from Center (O(n²))​

The Intuition​

What Happens with s = "babad":​

Complexity:​

Visualization:​

2. Top-Down DP (Memoization - O(n²))​

The Intuition​

What Happens with s = "babad":​

Memoization Table:​

Complexity:​

3. Bottom-Up DP (Tabulation - O(n²))​

The Intuition​

What Happens with s = "babad":​

DP Table Evolution:​

Complexity:​

Quick Comparison​

The Evolution​

Approach 1 → Approach 2:​

Approach 2 → Approach 3:​

Mental Models​

Which Approach to Use?​

Use Expand from Center when:​

Use Memoization when:​

Use Tabulation when:​

Complete Working Example​

Common Pitfalls​

Pitfall 1: Off-by-one errors in expand approach​

Pitfall 2: Not handling even-length palindromes​

Pitfall 3: Wrong base case in DP​

Practice Extensions​

Key Takeaways​

The Big Picture​

Understanding the Problem

1. Pure Recursion with Expand from Center (O(n²))

The Intuition

What Happens with `s = "babad"`:

Complexity:

Visualization:

2. Top-Down DP (Memoization - O(n²))

The Intuition

What Happens with `s = "babad"`:

Memoization Table:

Complexity:

3. Bottom-Up DP (Tabulation - O(n²))

The Intuition

What Happens with `s = "babad"`:

DP Table Evolution:

Complexity:

Quick Comparison

The Evolution

Approach 1 → Approach 2:

Approach 2 → Approach 3:

Mental Models

Which Approach to Use?

Use Expand from Center when:

Use Memoization when:

Use Tabulation when:

Complete Working Example

Common Pitfalls

Pitfall 1: Off-by-one errors in expand approach

Pitfall 2: Not handling even-length palindromes

Pitfall 3: Wrong base case in DP

Practice Extensions

Key Takeaways

The Big Picture