Longest Palindromic Substring

mediumTrie & Strings72 stepsJava · Python · C++

Find the longest palindromic substring. Expand from each of the 2n−1 centres while the ends match, and remember the widest expansion seen.

▶ Watch the animated trace

Traced input: s = "babad" → "bab". Original problem: neetcode.io/problems/longest-palindromic-substring

Complexity

BestO(n)

AverageO(n²)

WorstO(n²)

SpaceO(1)

Manacher's algorithm does O(n), but it's rarely expected.

Key idea

Odd palindromes centre on a character; even ones on a gap.
Expansion returns the length; convert it back to a start index.
Keep only the best start and length, not the substring.

Common mistakes

Forgetting even-length centres.
Off-by-one when converting the expanded bounds back to a substring.

Solution

Java

String longestPalindrome(String s) {
    int bestStart = 0, bestLen = 1;
    for (int center = 0; center < 2 * s.length() - 1; center++) {
        int l = center / 2, r = l + center % 2;
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        int len = r - l - 1;
        if (len > bestLen) {
            bestLen = len;
            bestStart = l + 1;
        }
    }
    return s.substring(bestStart, bestStart + bestLen);
}

Python

def longestPalindrome(s: str) -> str:
    best_start, best_len = 0, 1
    for center in range(2 * len(s) - 1):
        l, r = center // 2, center // 2 + center % 2
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        if r - l - 1 > best_len:
            best_len = r - l - 1
            best_start = l + 1
    return s[best_start:best_start + best_len]

C++

string longestPalindrome(string s) {
    int bestStart = 0, bestLen = 1, n = s.size();
    for (int center = 0; center < 2 * n - 1; center++) {
        int l = center / 2, r = l + center % 2;
        while (l >= 0 && r < n && s[l] == s[r]) {
            l--;
            r++;
        }
        int len = r - l - 1;
        if (len > bestLen) {
            bestLen = len;
            bestStart = l + 1;
        }
    }
    return s.substr(bestStart, bestLen);
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Even palindrome Only the gap centre finds it.	`s = "cbbd"`	`"bb"`
Single character Itself.	`s = "a"`	`"a"`
Whole string The centre 'e' expands to both ends.	`s = "racecar"`	`"racecar"`