Longest Palindromic Substring

MediumDynamic Programming (1-D & 2-D)Blind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given a string s. Return the longest substring of s that reads the same forward and backward. A substring is a contiguous run of characters, so you can't skip letters. If several palindromes share the maximum length, returning any one of them is accepted. A single character counts as a palindrome, so the answer is never empty.

Examples

s = "babad" returns "bab"

"aba" is just as long and also accepted. No substring of length 4 or 5 reads the same both ways.

s = "cbbd" returns "bb"

"bb" is the only palindrome longer than one character. It has even length, so there is no single middle letter.

Constraints

1 <= s.length <= 1000
s consists of only digits and English letters.

Hints

Hint 1

A palindrome looks the same from its middle outward. How many possible middles does a string have?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

A palindrome mirrors around its middle, and a string of length n has 2n - 1 possible middles: each character (odd length) and each gap between neighbors (even length). From each middle, expand outward while the two end characters match, and keep the widest window found. Each expansion is O(n), so the total is O(n^2) time and O(1) extra space. The 2-D table version (s[i..j] is a palindrome if s[i] == s[j] and s[i+1..j-1] is one) has the same time but O(n^2) space.

Time

O(n^2)

Space

O(1)

Pitfall

Expanding only around single characters. That finds odd-length palindromes only, so "cbbd" returns "c" instead of "bb"; you also need a middle between every pair of neighbors.

Solutions

class Solution {
    public String longestPalindrome(String s) {
        int start = 0, end = 0; // best window is s[start..end], inclusive
        for (int i = 0; i < s.length(); i++) {
            int len = Math.max(expand(s, i, i), expand(s, i, i + 1));
            if (len > end - start + 1) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    // Grows s[left..right] while it stays a palindrome; returns its length.
    private int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left: int, right: int) -> tuple[int, int]:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return left + 1, right  # the palindrome is s[left + 1:right]

        best_lo, best_hi = 0, 1
        for i in range(len(s)):
            for lo, hi in (expand(i, i), expand(i, i + 1)):
                if hi - lo > best_hi - best_lo:
                    best_lo, best_hi = lo, hi
        return s[best_lo:best_hi]