Leetcode 5. Longest Palindromic Substring

Let's understand what we're being asked to do. Given a string like 'babad', we need to find the longest substring that reads the same forwards and backwards.

Tracing through: 'bab' is a palindrome (reads same both ways), 'aba' is also a palindrome, but 'bad' is not (backwards is 'dab'). Both 'bab' and 'aba' have length 3, so either is a valid answer.

Important constraint: A palindrome can have odd length (like 'aba' with center 'b') or even length (like 'abba' with center between the two 'b's). We need to handle both cases!

Edge cases to consider: What if the entire string is a palindrome? What if no palindrome exists longer than 1 character? What if the string has length 1?

The brute force approach generates all possible substrings and checks each one to see if it's a palindrome. For each starting position, try all possible ending positions, extract the substring, and verify if it reads the same forwards and backwards. Keep track of the longest palindrome found. This approach is simple but inefficient because it examines every possible substring.

def longest_palindrome(s):
    """
    Find the longest palindromic substring using brute force.
    Check every possible substring to see if it's a palindrome.
    """
    if not s:
        return ""
    
    longest = ""
    n = len(s)
    
    # Try every possible starting position
    for start in range(n):
        # Try every possible ending position from this start
        for end in range(start, n):
            # Extract substring
            substring = s[start:end + 1]
            
            # Check if this substring is a palindrome
            is_palindrome = True
            left = 0
            right = len(substring) - 1
            
            while left < right:
                if substring[left] != substring[right]:
                    is_palindrome = False
                    break
                left += 1
                right -= 1
            
            # Update longest if this palindrome is longer
            if is_palindrome and len(substring) > len(longest):
                longest = substring
    
    return longest

Every palindrome has a center point from which it expands symmetrically. For 'aba', the center is 'b'. For 'abba', the center is between the two 'b's.

This means we can check each possible center position and expand outward while characters match, rather than checking every possible substring.

By expanding around centers, we avoid checking all possible substrings. Instead of examining every start-end pair (which would be O(n²) pairs, each taking O(n) to verify), we check O(n) possible centers and expand each in O(n) time.

This transforms a potentially O(n³) brute force approach into an O(n²) solution.

Think of dropping a pebble in water - ripples expand outward symmetrically. A palindrome works the same way: from a center, characters must match as you move outward.

For a string of length n, there are 2n-1 possible centers: n single-character centers (odd-length palindromes) and n-1 between-character centers (even-length palindromes). Check each center and expand while characters match.

The optimal approach uses the expand-around-center technique. For each possible center position (both single characters for odd-length palindromes and between characters for even-length palindromes), expand outward while the characters on both sides match. Track the longest palindrome found during all expansions. This efficiently finds palindromes by leveraging their symmetric property without checking every possible substring.

def longest_palindrome(s):
    """
    Find the longest palindromic substring using expand-around-center.
    Time: O(n^2), Space: O(1)
    """
    if not s:
        return ""
    
    # Track the longest palindrome found
    start = 0
    max_len = 0
    
    # Helper function to expand around center
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        # Return length of palindrome
        return right - left - 1
    
    # Check each possible center
    for i in range(len(s)):
        # Odd length palindromes (single character center)
        len1 = expand_around_center(i, i)
        # Even length palindromes (between two characters)
        len2 = expand_around_center(i, i + 1)
        
        # Get the longer palindrome
        current_len = max(len1, len2)
        
        # Update if we found a longer palindrome
        if current_len > max_len:
            max_len = current_len
            # Calculate start position of palindrome
            start = i - (current_len - 1) // 2
    
    # Extract and return the longest palindrome
    return s[start:start + max_len]

• Expand-around-center technique: Palindromes have natural symmetry around a center point - instead of checking every substring, expand outward from each possible center (O(n) centers × O(n) expansion = O(n²)). This transforms a naive O(n³) brute-force into an efficient O(n²) solution by exploiting structural properties.
• Odd vs even length handling: Palindromes can have either a single-character center (odd length like "aba") or a two-character center (even length like "abba") - you must check both cases at each position by calling expand with (i, i) and (i, i+1) to avoid missing half of all possible palindromes.
• Two-pointer expansion pattern: Use left and right pointers moving outward while characters match (while left >= 0 && right < n && s[left] == s[right]) - this bounded expansion naturally handles edge cases and stops at the first mismatch, giving you the exact palindrome boundaries.
• String slicing vs index tracking: Instead of creating substrings during expansion (expensive), track only the start index and maximum length found - only slice once at the end using s.substring(maxStart, maxStart + maxLen) to avoid O(n) string copies in the inner loop.
• Center-based optimization over DP: While dynamic programming works (O(n²) time, O(n²) space), expand-around-center achieves the same time complexity with O(1) space by computing palindromes on-demand rather than storing a full DP table - prefer space-efficient solutions when time complexity is equivalent.
• Pattern recognition for symmetry problems: Whenever a problem involves finding symmetric structures (palindromes, mirror patterns, balanced sequences), consider center-expansion or two-pointer approaches - symmetry naturally suggests working from the middle outward or edges inward rather than left-to-right scanning.