Problem statement

Given a string s, return the longest palindromic substring. If several palindromes share the maximum length, return the leftmost one.

Example 1

Input: s = "babad"
Output: "bab"
Explanation: Both "bab" and "aba" have length 3; "bab" starts first.

Example 2

Input: s = "cbbd"
Output: "bb"

Constraints

• 1 <= s.length <= 30
• s consists of lowercase English letters.

Hints for Longest Palindromic Substring

1. Hint 1

   Every palindrome has a center — a character or a gap between two characters.

2. Hint 2

   Expand around all 2n-1 centers and keep the first longest.

How to solve Longest Palindromic Substring

Every palindrome has a centre, and there are only 2n - 1 of them — n single characters plus n - 1 gaps between characters. Try each centre, expand outward while the two sides match, and keep the longest span found.

Approach

1. For each index, expand around it as an odd-length centre (l = r = i).
2. Also expand around the gap after it as an even-length centre (l = i, r = i + 1).
3. In each expansion, widen while both ends are in bounds and the characters match.
4. When expansion stops, the palindrome spans l + 1 .. r - 1, of length r - l - 1.
5. Keep the span only when it is strictly longer than the best so far, which preserves the leftmost on ties.

Why it works

Every palindromic substring is produced by exactly one centre, so trying all centres examines every candidate — and expansion from a centre finds the longest palindrome around it, since the moment the ends disagree no wider span can be symmetric. Scanning centres left to right and updating only on a strict improvement is what makes the leftmost maximal palindrome win a tie.

Complexity

• Time — O(n^2)
• Space — O(1)

Pitfalls

• Even-length palindromes need their own centre between characters — checking only single-character centres misses "bb" entirely.
• After the expansion loop, the bounds have already overshot by one on each side, so the length is r - l - 1.
• Use a strict > when updating the best, or a later equal-length palindrome overwrites the leftmost one.
• Manacher's algorithm solves this in linear time, but is far more delicate to write.

Reference solution

Python

def longestPalindrome(s: str) -> str:
    best = ""
    for c in range(len(s)):
        for l0, r0 in ((c, c), (c, c + 1)):
            l, r = l0, r0
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            cand = s[l + 1:r]
            if len(cand) > len(best):
                best = cand
    return best

Java

public static String longestPalindrome(String s) {
    int n = s.length();
    int[] best = new int[]{0, 1};
    for (int i = 0; i < n; i++) {
        expandLP(s, i, i, best);
        expandLP(s, i, i + 1, best);
    }
    return s.substring(best[0], best[0] + best[1]);
}

private static void expandLP(String s, int lo, int hi, int[] best) {
    int n = s.length();
    int l = lo, r = hi;
    while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
        l--;
        r++;
    }
    int len = r - l - 1;
    if (len > best[1]) {
        best[1] = len;
        best[0] = l + 1;
    }
}

C++

void expandLP(const string& s, int lo, int hi, int& bestStart, int& bestLen) {
    int n = (int) s.size();
    int l = lo, r = hi;
    while (l >= 0 && r < n && s[l] == s[r]) {
        l--;
        r++;
    }
    int len = r - l - 1;
    if (len > bestLen) {
        bestLen = len;
        bestStart = l + 1;
    }
}

string longestPalindrome(string s) {
    int bestStart = 0, bestLen = 1;
    for (int i = 0; i < (int) s.size(); i++) {
        expandLP(s, i, i, bestStart, bestLen);
        expandLP(s, i, i + 1, bestStart, bestLen);
    }
    return s.substr(bestStart, bestLen);
}

JavaScript

var longestPalindrome = function(s) {
    let best = "";
    for (let c = 0; c < s.length; c++) {
        for (const [l0, r0] of [[c, c], [c, c + 1]]) {
            let l = l0, r = r0;
            while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
            const cand = s.slice(l + 1, r);
            if (cand.length > best.length) best = cand;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium