Expand Around Center: Longest Palindromic Substring

Hello! In our last few lessons, we've gone deep into dynamic programming, culminating in an optimized $O(N\log N)$ solution for the Longest Increasing Subsequence problem. That was a problem about subsequences, where elements can be non-contiguous.

Today, we're shifting our focus to a related but distinct category: substrings, which must be contiguous. We'll tackle one of the most classic problems in this space: finding the Longest Palindromic Substring. You'll learn a highly intuitive and efficient pattern called "expand around center," which leverages the inherent symmetry of palindromes. This lesson will not only equip you to solve this specific problem but also strengthen your ability to recognize when a two-pointer approach can simplify problems involving symmetric structures.

1. The Problem: Substrings, Palindromes, and Efficiency

The task is to find the longest substring within a given string that is a palindrome. A palindrome is a sequence that reads the same forwards and backward, like "racecar" or "madam". For example, in the string "babad", both "bab" and "aba" are longest palindromic substrings of length 3.

A simple brute-force approach would be to generate every possible substring, check if it's a palindrome, and keep track of the longest one found. This would involve $O(N^2)$ substrings, and checking each one takes $O(N)$ time, leading to an overall time complexity of $O(N^3)$. For typical constraints in an interview setting (e.g., $N\le 1000$), this is too slow.

While a dynamic programming solution exists with $O(N^2)$ time and $O(N^2)$ space, there's an even more elegant approach that achieves the same time complexity with only $O(1)$ space. This method, "expand around center," is often preferred in interviews for its efficiency and clarity.

The following video offers a great perspective on why this approach is a practical choice for interviews compared to DP or the more complex Manacher's algorithm.

2. The "Expand Around Center" Technique

The core insight behind this technique is that every palindrome has a center. Instead of checking every substring, we can iterate through all possible centers and expand outwards to find the longest palindrome for each center.

A key detail is that a center can be one of two types:

1. A single character: This applies to odd-length palindromes like "racecar", where 'e' is the center.
2. The space between two characters: This applies to even-length palindromes like "abba", where the center is between the two 'b's.

For a string of length $N$, there are $N$ possible single-character centers and $N-1$ possible centers between characters, giving us a total of $2N-1$ potential centers to check.

The article below provides a concise explanation of this idea.

3. Implementation and Walkthrough

Let's put this all together into a complete algorithm. We will iterate through each index i from 0 to N-1. For each i, we will find the longest palindrome centered at i (odd length) and the longest palindrome centered between i and i+1 (even length). We'll keep track of the longest one we've seen so far.

Here is the Python implementation, closely following the structure from the Hello Interview resource you just read.

def longestPalindrome(s: str) -> str:
    if not s or len(s) < 1:
        return ""

    start = 0
    max_len = 0

    def expand_around_center(left: int, right: int) -> int:



        # Use two pointers to expand outwards from the center
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1



        # The palindrome's length is (right - 1) - (left + 1) + 1
        return right - left - 1

    for i in range(len(s)):



        # Odd length palindromes, center is at s[i]
        len1 = expand_around_center(i, i)
        



        # Even length palindromes, center is between s[i] and s[i+1]
        len2 = expand_around_center(i, i + 1)
        
        current_len = max(len1, len2)
        
        if current_len > max_len:
            max_len = current_len



            # This calculation finds the correct start index
            # based on the center 'i' and the palindrome's length.
            start = i - (current_len - 1) // 2
            
    return s[start : start + max_len]




# Example
print(longestPalindrome("babad")) # Output: "bab" or "aba"
print(longestPalindrome("cbbd"))  # Output: "bb"

Code Breakdown:

• expand_around_center(left, right): This helper function takes two pointers, left and right, defining the initial center. It expands them outwards as long as they are within the string's bounds and the characters they point to are equal. It returns the length of the palindrome found.
• Main Loop: The loop iterates through every possible character i to serve as a pivot for the center.
• Odd/Even Cases: expand_around_center(i, i) seeds the search for an odd-length palindrome. expand_around_center(i, i + 1) seeds the search for an even-length one.
• Tracking the Result: start and max_len are updated whenever a longer palindrome is found. The calculation start = i - (current_len - 1) // 2 is a key detail. It correctly backtracks from the center i to find the starting index of the new longest palindrome.

The NeetCode video below provides an excellent visual walkthrough of this implementation logic.

4. Complexity Analysis and Final Thoughts

Let's analyze the performance of our solution.

• Time Complexity: $O(N^2)$
  We have a single loop that iterates through $N$ characters of the string. Inside this loop, we call expand_around_center twice. In the worst-case scenario (a string that is itself a palindrome, like "aaaaaaaa"), each expansion can take up to $O(N)$ time. This gives us a total time complexity of $O(N\times N)=O(N^2)$.

• Space Complexity: $O(1)$
  The beauty of this approach is its space efficiency. We only use a few variables (start, max_len, left, right, etc.) to keep track of pointers and the result. The amount of space used does not grow with the size of the input string, so the space complexity is constant.

This makes the expand-around-center approach a superior choice over the $O(N^2)$ space DP solution, especially when memory is a concern or when an interviewer is looking for a space-optimized algorithm.

Conclusion

In this lesson, we explored the "Longest Palindromic Substring" problem and solved it using the elegant expand-around-center technique. This approach is a fantastic example of leveraging a problem's inherent structure—in this case, symmetry—to devise an efficient algorithm.

Key Takeaways:

• Pattern Recognition: Problems involving palindromes or other symmetric structures are often prime candidates for a two-pointer approach that either moves inwards from the edges or expands outwards from the center.
• Handling All Cases: A critical part of this pattern is to correctly identify and handle all possible centers. For palindromes, this means considering both single-character (odd length) and between-character (even length) centers.
• Space Optimization: The expand-around-center method achieves the same $O(N^2)$ time complexity as a standard DP solution but drastically reduces the space complexity from $O(N^2)$ to $O(1)$.
• Index Tracking: A practical implementation detail is to track the start index and max_len of the result rather than creating new substring objects in every step of the loop, which would be inefficient.

We have now seen a DP approach for a subsequence problem (LIS) and a two-pointer approach for a substring problem (Longest Palindromic Substring). In our next lesson, we will synthesize these experiences to build a mental model for how to distinguish between subsequence and substring problems and quickly select the most appropriate algorithmic pattern.