Longest Palindromic Substring

Problem Description

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

Examples

Constraints

• 1 ≤ s.length ≤ 1000
• s consists of only digits and English letters.

Expanding Outward from Center Coordinates

The naive approach is checking all O(n²) substrings for palindromes. Checking a substring of length k takes O(k) time, making the total complexity O(n³).

To optimize, note that a palindrome is symmetric. Instead of scanning substrings from the outside in, we can start at a center index and expand outward as long as the boundary characters match.

• For odd-length palindromes, the center is a single character (e.g. 'a' in "aba").
• For even-length palindromes, the center lies between two characters (e.g. the gap between 'b' and 'b' in "abba").

Since there are 2n - 1 possible centers, and expanding from a center takes O(n) time, the total complexity is O(n²) time with O(1) auxiliary space.

Solution 1: Expand Around Center (Optimal Space)

Iterate through all possible centers, expanding outward to find the maximum palindrome length.

class Solution {
    private int maxLen = 0;
    private int startIdx = 0;

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

        for (int i = 0; i < s.length(); i++) {
            expand(s, i, i);     // odd-length center
            expand(s, i, i + 1); // even-length center
        }
        return s.substring(startIdx, startIdx + maxLen);
    }

    private void expand(String s, int left, int right) {
        // expand as long as characters match and indices are in bounds
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // length of matched palindrome is (right - 1) - (left + 1) + 1 = right - left - 1
        int len = right - left - 1;
        if (len > maxLen) {
            maxLen = len;
            startIdx = left + 1; // start index of palindrome is left + 1
        }
    }
}

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2:
            return s

        start_idx = 0
        max_len = 0

        def expand(left, right):
            nonlocal start_idx, max_len
            # expand as long as characters match
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # length is right - left - 1
            length = right - left - 1
            if length > max_len:
                max_len = length
                start_idx = left + 1

        for i in range(len(s)):
            expand(i, i)  # odd-length center
            expand(i, i + 1)  # even-length center

        return s[start_idx : start_idx + max_len]

#include <string>
#include <algorithm>

class Solution {
private:
    int startIdx = 0;
    int maxLen = 0;

    void expand(const std::string& s, int left, int right) {
        // expand as long as characters match
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            left--;
            right++;
        }
        int len = right - left - 1;
        if (len > maxLen) {
            maxLen = len;
            startIdx = left + 1;
        }
    }

public:
    std::string longestPalindrome(std::string s) {
        if (s.length() < 2) return s;

        for (int i = 0; i < s.length(); i++) {
            expand(s, i, i);     // odd-length center
            expand(s, i, i + 1); // even-length center
        }
        return s.substr(startIdx, maxLen);
    }
};

Complexity Analysis:

• Time Complexity: O(n²) where n is the length of string s. We expand from 2n - 1 centers, taking up to O(n) steps per expansion.
• Space Complexity: O(1) auxiliary space as we do not allocate extra matrices.

Where it breaks: If the string length is extremely large (e.g. 10⁵), this O(n²) solution is too slow. For linear time O(n) performance, Manacher’s Algorithm is required. Manacher’s is rarely expected in interviews due to its implementation complexity.

Common Mistakes

• Only checking odd-length centers. If you omit the expand(i, i + 1) check, your code will fail to find even-length palindromes like "cbbd" (returning "c" or "b" instead of "bb").
• Incorrectly calculating the palindrome slice length. After the while loop terminates, pointers left and right have stepped past the matching boundary. The correct length is right - left - 1, and the starting index is left + 1.
• String copying during expansion. In C++, pass the string parameter by const reference (const std::string& s) to avoid copying it on every call, which increases memory overhead.

Frequently Asked Questions

Is there a way to solve this in O(n) time? Yes. Manacher’s Algorithm solves this problem in O(n) time and O(n) space. It uses pre-computed palindrome boundary states to skip redundant expansions, but is highly complex to write.

How does this compare to a dynamic programming matrix solution? A DP solution uses a boolean matrix dp[i][j] representing if s[i..j] is a palindrome. This runs in O(n²) time but requires O(n²) space. The expand-around-center approach is superior because it uses O(1) space.

What does this problem test in interviews? It tests your ability to optimize search loops, coordinate boundary pointers, and handle even/odd center cases.

← All Problems