MediumTwo PointersStringDynamic Programming

Longest Palindromic Substring

1 approach, code in every language

Given a string, find the longest contiguous slice of it that is a palindrome, meaning it reads identically in both directions.

If several substrings share the maximum length, returning any one of them is acceptable. A single character is trivially a palindrome, so the answer is never empty when the input is non-empty.

Example 1

Input: s = "babad"

Output: "bab"

The slice "bab" is a palindrome of length three; "aba" would also be a valid answer.

Example 2

Input: s = "cbbd"

Output: "bb"

The longest mirror-image slice is "bb", since no palindrome of length three or more exists here.

Constraints

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

Expand Around Each Center

Treat every index (and every gap between two indices) as the middle of a potential palindrome and grow outward as long as the mirrored characters match, keeping track of the widest span seen.

Loading animation…

Intuition

Every palindrome has a center: for odd lengths it is a single character, and for even lengths it is the seam between two characters. If we fix that center and push two pointers apart, the substring stays a palindrome exactly while the characters on either side keep matching. By trying all 2n - 1 possible centers and expanding each one, we are guaranteed to discover the longest palindrome without checking every substring explicitly.

Algorithm walkthrough

1Track the best starting index and best length found so far, initialized to the first character.
2For each position in the string, consider two centers: the character itself (odd length) and the gap just after it (even length).
3From each center, move a left pointer down and a right pointer up while both stay in bounds and the characters they point to are equal.
4Whenever an expansion yields a span longer than the current best, record its start index and length.
5After examining every center, return the substring described by the best start index and length.

Implementation

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        best_start, best_len = 0, 1

        def expand(left: int, right: int) -> None:
            nonlocal best_start, best_len
            while left >= 0 and right < len(s) and s[left] == s[right]:
                if right - left + 1 > best_len:
                    best_len = right - left + 1
                    best_start = left
                left -= 1
                right += 1

        for center in range(len(s)):
            expand(center, center)
            expand(center, center + 1)
        return s[best_start:best_start + best_len]

Time

O(n^2)

Space

O(1)

There are about 2n centers and each expansion runs in linear time, while only a few counters are stored.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Strings

After the pattern

Now solve one you haven't seen.

Longest Mirror Run is our own problem on the technique behind Longest Palindromic Substring: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free