Longest Palindromic Substring

LeetCode 5: Longest Palindromic Substring Solution & Explanation

Problem Overview

TL;DR: Iterate through every possible palindrome center in the string and expand two pointers outwards to find the maximum length palindrome.

The Longest Palindromic Substring problem asks us to identify the longest contiguous sequence within a given string s that reads the same forwards and backwards. If multiple substrings have the same maximum length, returning any one of them is acceptable. This is a classic string manipulation problem and a popular interview question that tests your understanding of string properties and pointer manipulation.

Brute Force Approach for Longest Palindromic Substring

The naive approach involves generating every possible substring and verifying if it is a palindrome.

1. Use nested loops to define the start (i) and end (j) of every substring.
2. For each substring defined by s[i...j], iterate from the ends towards the middle to check if characters match.
3. Track the maximum length found.

Pseudo-code:

max_str = ""
for i from 0 to length(s):
    for j from i to length(s):
        substring = s[i...j]
        if isPalindrome(substring) and len(substring) > len(max_str):
            max_str = substring
return max_str

Complexity Analysis: The number of substrings is $O(N^2)$. Verifying each substring takes $O(N)$ time.

• Time Complexity: $O(N^3)$.
• Space Complexity: $O(1)$ (excluding result storage).

Why it fails: With a constraint of s.length <= 1000, an $O(N^3)$ solution performs roughly $10^9$ operations, which typically results in a Time Limit Exceeded (TLE) error. We need a more efficient approach to handle the constraints of LeetCode 5.

Algorithm Strategy: Two Pointers Patterns

The strategy relies on iterating through the string and invoking an expansion helper function for both odd and even cases.

1. State Management: Maintain variables to track the starting index and the length of the longest palindrome found so far.
2. Iterative Expansion: Iterate through the string with index i from 0 to n-1.
   • Case 1 (Odd): Treat i as the center. Initialize left = i, right = i. Expand.
   • Case 2 (Even): Treat i and i+1 as the center. Initialize left = i, right = i + 1. Expand.
3. Boundary Constraints: During expansion, ensure left >= 0 and right < s.length.
4. Update Logic: After each expansion, check if the length of the current palindrome exceeds the stored maximum. If so, update the start index and max length.
5. Result: Extract the substring using the final start index and max length.

Execution Flow

1. Initialize start = 0 and maxLen = 0.
2. Loop i from 0 to s.length - 1:
   • Odd Expansion: Call expand(i, i).
     • While s[left] == s[right]: decrement left, increment right.
     • Calculate length: right - left - 1.
     • If length > maxLen, update maxLen and start.
   • Even Expansion: Call expand(i, i+1).
     • While s[left] == s[right]: decrement left, increment right.
     • Calculate length: right - left - 1.
     • If length > maxLen, update maxLen and start.
3. Return substring s[start ... start + maxLen].

Note: The length calculation right - left - 1 works because the while loop terminates after the pointers have moved past the valid palindrome boundaries.

Proof of Correctness

The algorithm is correct because every palindromic substring must have a center. By explicitly checking every possible center (both characters and gaps between characters) and expanding maximally from those centers, we are guaranteed to find the globally optimal solution. The expansion process ensures that for any center, the longest possible palindrome rooted at that center is identified. Since we iterate through all $2N-1$ centers, the global maximum is found.

Pattern Reuse Notes

The "Two Pointers - Expanding From Center" pattern is highly reusable for palindrome-related problems.

• LeetCode 647: Palindromic Substrings
  • Similarity: Instead of finding the longest palindrome, this problem asks you to count all palindromic substrings. The logic is identical: iterate through all centers and increment a counter for every successful expansion step.

Reference Implementation

C++ Solution for LeetCode 5

1class Solution {
2public:
3    string longestPalindrome(string s) {
4        if (s.empty()) return "";
5        
6        int start = 0;
7        int maxLen = 0;
8        
9        for (int i = 0; i < s.length(); ++i) {
10            // Odd length palindromes (single character center)
11            int len1 = expandAroundCenter(s, i, i);
12            // Even length palindromes (two character center)
13            int len2 = expandAroundCenter(s, i, i + 1);
14            
15            int len = max(len1, len2);
16            
17            if (len > maxLen) {
18                maxLen = len;
19                // Calculate start index based on length and center
20                start = i - (len - 1) / 2;
21            }
22        }
23        
24        return s.substr(start, maxLen);
25    }
26    
27private:
28    int expandAroundCenter(const string& s, int left, int right) {
29        while (left >= 0 && right < s.length() && s[left] == s[right]) {
30            left--;
31            right++;
32        }
33        // Return length of the palindrome
34        // (right - 1) - (left + 1) + 1 = right - left - 1
35        return right - left - 1;
36    }
37};

Java Solution for LeetCode 5

1class Solution {
2    public String longestPalindrome(String s) {
3        if (s == null || s.length() < 1) return "";
4        
5        int start = 0;
6        int end = 0;
7        
8        for (int i = 0; i < s.length(); i++) {
9            // Expand for odd length (center is i)
10            int len1 = expandAroundCenter(s, i, i);
11            // Expand for even length (center is i, i+1)
12            int len2 = expandAroundCenter(s, i, i + 1);
13            
14            int len = Math.max(len1, len2);
15            
16            // If we found a longer palindrome, update boundaries
17            if (len > end - start) {
18                start = i - (len - 1) / 2;
19                end = i + len / 2;
20            }
21        }
22        
23        // substring in Java is [start, end)
24        return s.substring(start, end + 1);
25    }
26    
27    private int expandAroundCenter(String s, int left, int right) {
28        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
29            left--;
30            right++;
31        }
32        // Return length. Pointers are currently one step outside the valid range.
33        return right - left - 1;
34    }
35}

Python Solution for LeetCode 5

1class Solution:
2    def longestPalindrome(self, s: str) -> str:
3        if not s:
4            return ""
5        
6        start = 0
7        max_len = 0
8        
9        for i in range(len(s)):
10            # Odd length palindromes
11            len1 = self.expand_around_center(s, i, i)
12            # Even length palindromes
13            len2 = self.expand_around_center(s, i, i + 1)
14            
15            length = max(len1, len2)
16            
17            if length > max_len:
18                max_len = length
19                # Calculate new start index
20                start = i - (length - 1) // 2
21                
22        return s[start : start + max_len]
23    
24    def expand_around_center(self, s: str, left: int, right: int) -> int:
25        while left >= 0 and right < len(s) and s[left] == s[right]:
26            left -= 1
27            right += 1
28        # Length calculation
29        return right - left - 1