Longest Palindromic Substring

+10

You get a string s of lowercase English letters. Return its longest palindromic substring: the longest run of consecutive letters that reads the same forward and backward. If several substrings share that longest length, return the one that starts furthest to the left.

Function

longestPalindrome(s: string) → string

sstring: the lowercase string to search
Returnsstring: the longest palindromic substring of s, the leftmost one when several tie

Constraints

1 ≤ s.length ≤ 2000
s holds only lowercase English letters.
When several palindromes have the longest length, the answer is the one with the smallest start index.

Examples

Input: s = "bananas"
Output: "anana"
Explanation: "anana" reads the same from both ends and has 5 letters. No longer piece works: "banana" starts with b and ends with a, "ananas" starts with a and ends with s, and the whole word starts with b and ends with s.

Input: s = "xyzzyabba"
Output: "yzzy"
Explanation: "yzzy" and "abba" are both palindromes of length 4, and nothing longer exists. "yzzy" starts at index 1, before "abba" at index 5, so it wins the tie.

Input: s = "abcd"
Output: "a"
Explanation: No two letters are equal, so every palindrome is a single letter. The leftmost one is "a".

+18 hidden tests on Submit

Follow-up

Can you find the answer in O(n) time?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A palindrome mirrors around its middle, and that middle is either one letter (odd length, like "anana") or the gap between two equal letters (even length, like "abba"). Checking every substring on its own ignores that structure and costs O(n³). Growing each palindrome outward from its middle reuses every comparison, which brings the search down to O(n²) time with O(1) extra memory.

Check every substring

Correct, but does not finish on the largest tests

Intuition

A substring is fixed by its first index i and its last index j. Test it with two pointers: compare s[i] with s[j], then s[i+1] with s[j-1], and so on, stopping at the first mismatch. If the pointers meet or cross without one, the substring is a palindrome. Keep the longest you find.

For the tie rule, walk the starts from left to right and replace the best only when a new palindrome is strictly longer. A later palindrome of the same length then never pushes out an earlier one, so you return the leftmost.

This looks at all n(n+1)/2 substrings, so it cannot miss the answer. It is slow because each test can walk half the substring. For a string of 2000 copies of a, every substring is a palindrome and every test runs to the middle: about n³/12 ≈ 6.7 × 10^8 letter comparisons.

Algorithm

Start with the first letter as the best: start 0, length 1.
For each start i and each end j ≥ i, compare letters from both ends toward the middle until they differ or the pointers meet.
If the pointers met without a mismatch, s[i..j] is a palindrome.
If its length j-i+1 beats the best, record i and that length.
Return the substring at the best start with the best length.

def longestPalindrome(s):
    n = len(s)
    best_start, best_len = 0, 1
    for i in range(n):
        for j in range(i, n):
            # Compare s[i..j] from both ends toward the middle
            left, right = i, j
            while left < right and s[left] == s[right]:
                left += 1
                right -= 1
            is_palindrome = left >= right
            if is_palindrome and j - i + 1 > best_len:
                best_start, best_len = i, j - i + 1
    return s[best_start:best_start + best_len]

Table of palindromes by length

Intuition

The brute force forgets what it learned. When it tests "anana" it compares a with a and then n with n, and the second comparison is the whole test of "nan", which it already ran. The rule that saves the work: s[i..j] is a palindrome when its two ends match and the part between them, s[i+1..j-1], is a palindrome. One comparison plus one stored answer settles each substring.

Store the answers in a table pal[i][j] and fill it by length. Every single letter is a palindrome. A two-letter substring is one when both letters match. For longer lengths, use the rule: the inside is two letters shorter, so its cell is already filled.

In "bananas", pal[1][5] ("anana") is true because s[1] and s[5] are both a and pal[2][4] ("nan") is true. Lengths go up and starts go from left to right, so the first palindrome of a new record length is also the leftmost of that length. About n²/2 cells cost O(1) each, so the time is O(n²); the price is memory, 4 × 10^6 cells for n = 2000.

Algorithm

Make an n × n table pal, all false.
For each length from 1 to n, and each start i whose end j = i+length-1 stays inside the string, check the two end letters.
Mark pal[i][j] when they match and the length is at most 2 or pal[i+1][j-1] is true.
When a marked cell's length beats the best, record i and the length.
Return the substring at the best start.

def longestPalindrome(s):
    n = len(s)
    # pal[i][j] is True when s[i..j] reads the same both ways
    pal = [[False] * n for _ in range(n)]
    best_start, best_len = 0, 1
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # Equal ends, and the part inside them is a palindrome (or too short to matter)
            if s[i] == s[j] and (length <= 2 or pal[i + 1][j - 1]):
                pal[i][j] = True
                if length > best_len:
                    best_start, best_len = i, length
    return s[best_start:best_start + best_len]

Expand around every center

Intuition

Every palindrome has a center. An odd-length one such as "anana" centers on a letter; an even-length one such as "abba" centers on the gap between its two middle letters. A string of length n has n letters and n-1 gaps, so 2n-1 possible centers.

From a center, step outward one letter on each side while the two letters match. Each step proves a palindrome two letters longer. The first mismatch, or the edge of the string, ends the walk, and nothing longer can share that center, because it would contain the mismatched pair. So one outward walk finds the longest palindrome around each center, and the longest of those is the answer.

In "bananas", start at the letter a at index 3. The letters at 2 and 4 are both n, the letters at 1 and 5 are both a, and the letters at 0 and 6 are b and s, so the walk stops with length 5. The start is 3 - (5-1)/2 = 1, which gives "anana". The same formula, center - (length-1)/2 rounded down, works for the gap centers too.

Walk the centers from left to right and replace the best only on a strictly longer length. Two palindromes of equal length have the same parity, and the one with the earlier center starts earlier, so the leftmost wins. The worst case is a string of one repeated letter: each center walks to the nearer edge, about n²/2 = 2 × 10^6 steps for n = 2000, and the memory is a few integers.

Algorithm

Write expand(left, right): while both indexes are inside the string and the letters match, move left down and right up. Return right-left-1.
For each center from 0 to n-1, take the larger of expand(center, center) and expand(center, center+1).
If that length beats the best, set the best start to center - (length-1)/2, rounded down, and the best length to it.
Return the substring at the best start with the best length.

def expand(s, left, right):
    # Grow outward while the two ends match; return the palindrome's length
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1


def longestPalindrome(s):
    best_start, best_len = 0, 1
    for center in range(len(s)):
        # Odd lengths grow from one letter, even lengths from the gap after it
        length = max(expand(s, center, center), expand(s, center, center + 1))
        if length > best_len:
            best_start = center - (length - 1) // 2
            best_len = length
    return s[best_start:best_start + best_len]

Pitfalls and edge cases

The idea is short, so the bugs hide in the details: the even centers, the length after the walk, the tie rule and the slicing.

Expanding only around letters misses every even palindrome. On "abba" that returns "a" instead of "abba".
The walk stops one step past each end, so the palindrome is s[left+1..right-1] with length right-left-1. Using right-left+1 adds two letters that do not match.
Replacing the best on an equal length returns the rightmost palindrome: "abba" instead of "yzzy" for "xyzzyabba".
For a gap center, center - length/2 is one too far left. In "xyzzyabba" the gap after index 2 has length 4, and the start is 2 - (4-1)/2 = 1, not 0.
Slicing APIs differ: C++ substr and C# Substring take a length, while JavaScript substring and Java substring take an end index.
In the table, filling rows by start from 0 upward reads pal[i+1][j-1] before it is filled. Fill by length, or walk the starts from the end.

Frequently asked questions4

What is the time complexity of Longest Palindromic Substring?

Expanding around centers takes O(n²) time and O(1) extra memory. The table approach is also O(n²) time but needs O(n²) memory, and checking every substring is O(n³). Manacher's algorithm reaches O(n), but interviewers rarely expect it.

Why does expand around center use 2n-1 centers?

An odd-length palindrome has a middle letter, and an even-length one has a middle gap between two equal letters. A string of n letters has n letters and n-1 gaps between neighbours. Expanding from only the letters misses palindromes like "abba".

What is Manacher's algorithm?

It finds the longest palindrome around every center in O(n) total time. It keeps the palindrome that reaches furthest right so far, and a center inside it starts from the answer of its mirror center, so no letter is compared again from scratch. It is worth knowing by name; expand around center is the solution interviewers usually want.

How is the longest palindromic substring different from the longest palindromic subsequence?

A substring is a run of consecutive letters, while a subsequence may skip letters. In "character" the longest palindromic substring is "ara", but "carac" is a palindromic subsequence of length 5. The subsequence version is solved with a table over (i, j) that drops one end when the two ends differ.

Python

def longestPalindrome(s):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

s = "bananas"

Expected

"anana"

Longest Palindromic Substring

Function

Constraints

Examples

Hints

Solution

Check every substring

Table of palindromes by length

Expand around every center

Pitfalls and edge cases

Frequently asked questions4

Similar problems