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.

Core Insight for Longest Palindromic Substring

The fundamental inefficiency of the brute force method is that it re-evaluates overlapping substrings independently. The "Expand From Center" pattern leverages the symmetric property of palindromes.

A palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center as long as the characters on the left and right are equal.

There are two types of centers to consider:

1. Odd-length palindromes: The center is a specific character (e.g., "aba", center is 'b').
2. Even-length palindromes: The center is the gap between two characters (e.g., "abba", center is between 'b' and 'b').

For a string of length $N$, there are $N$ single-character centers and $N-1$ two-character centers, resulting in $2N-1$ total centers. By expanding from each center, we reduce the complexity significantly compared to checking all substrings.

Visual Description: Imagine the string as an array of characters. The algorithm places two pointers, left and right. Initially, for an odd-length check, both pointers point to index i. For an even-length check, left points to i and right points to i+1. In each step, the algorithm compares s[left] and s[right]. If they match, left decrements and right increments, effectively widening the window. This continues until the characters mismatch or the pointers hit the array boundaries.

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.

Reference Implementation

C++ Solution for LeetCode 5

cpp
class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        
        int start = 0;
        int maxLen = 0;
        
        for (int i = 0; i < s.length(); ++i) {
            // Odd length palindromes (single character center)
            int len1 = expandAroundCenter(s, i, i);
            // Even length palindromes (two character center)
            int len2 = expandAroundCenter(s, i, i + 1);
            
            int len = max(len1, len2);
            
            if (len > maxLen) {
                maxLen = len;
                // Calculate start index based on length and center
                start = i - (len - 1) / 2;
            }
        }
        
        return s.substr(start, maxLen);
    }
    
private:
    int expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            left--;
            right++;
        }
        // Return length of the palindrome
        // (right - 1) - (left + 1) + 1 = right - left - 1
        return right - left - 1;
    }
};

Java Solution for LeetCode 5

java
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        
        int start = 0;
        int end = 0;
        
        for (int i = 0; i < s.length(); i++) {
            // Expand for odd length (center is i)
            int len1 = expandAroundCenter(s, i, i);
            // Expand for even length (center is i, i+1)
            int len2 = expandAroundCenter(s, i, i + 1);
            
            int len = Math.max(len1, len2);
            
            // If we found a longer palindrome, update boundaries
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        
        // substring in Java is [start, end)
        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 length. Pointers are currently one step outside the valid range.
        return right - left - 1;
    }
}

Python Solution for LeetCode 5

python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        
        start = 0
        max_len = 0
        
        for i in range(len(s)):
            # Odd length palindromes
            len1 = self.expand_around_center(s, i, i)
            # Even length palindromes
            len2 = self.expand_around_center(s, i, i + 1)
            
            length = max(len1, len2)
            
            if length > max_len:
                max_len = length
                # Calculate new start index
                start = i - (length - 1) // 2
                
        return s[start : start + max_len]
    
    def expand_around_center(self, s: str, left: int, right: int) -> int:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        # Length calculation
        return right - left - 1