Longest Palindromic Substring

35 min · longestPalindrome()

A mirrored run can sit quietly inside a much longer message. Your job is to recover the largest one without rearranging or skipping a character.

Given a lowercase string s, return its longest palindromic substring. A substring is one continuous slice of the original string, and a palindrome reads the same in both directions.

Every input has exactly one substring of maximum palindromic length, so the returned string is unambiguous. Single characters count as palindromes.

Constraints

1 <= s.length <= 1_000
s contains only lowercase English letters.
Exactly one palindromic substring has the maximum length.

Hints

Start with every interval

The direct approach chooses each pair of boundaries and checks inward. Notice how often nearby intervals compare the same inner characters.

Reuse the inner answer

An interval is palindromic when its two ends match and its inside is palindromic. Fill shorter intervals before longer ones, or choose an order that guarantees the inner state is ready.

Search from the midpoint

Every palindrome has one center: either a character or a gap. Expand from all 2n - 1 centers and keep the widest successful interval.

Follow-up

Could you reach O(n) time? Manacher's algorithm is a method that reuses palindrome radii across neighboring centers to do exactly that.

Visible cases

Examples

Example 1

ready

Input: s = "cbbd"
Expected: "bb"
Why: the middle pair is the unique longest palindrome

Example 2

ready

Input: s = "a"
Expected: "a"
Why: a single character is already palindromic

Example 3

ready

Input: s = "forgeeksskeegfor"
Expected: "geeksskeeg"
Why: the mirrored middle block is longest

Interview signal

Asked at

AmazonMicrosoftGoogle

Check every substring

Choose every interval, test it from both ends, and keep the longest palindrome found. The helper compares through the original string, so it doesn't allocate a copy for each candidate.

def longest_palindrome(s: str) -> str:
    def is_palindrome(left: int, right: int) -> bool:
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True
 
    best_start = 0
    best_length = 1
 
    for left in range(len(s)):
        for right in range(left, len(s)):
            length = right - left + 1
            if is_palindrome(left, right) and length > best_length:
                best_start = left
                best_length = length
 
    return s[best_start:best_start + best_length]

Time O(n³) for O(n²) intervals that can each take O(n) comparisons. Space O(1) apart from the returned slice.

Palindrome DP — build from the inside out

Dynamic programming (DP) stores answers to overlapping smaller problems. Let is_pal[left][right] record whether one interval is a palindrome. Matching ends form a palindrome when the interval has length at most 2 or its inner interval is already known to be palindromic.

def longest_palindrome(s: str) -> str:
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
    best_start = 0
    best_length = 1
 
    for left in range(n - 1, -1, -1):
        for right in range(left, n):
            short = right - left <= 1
            if s[left] == s[right] and (short or is_pal[left + 1][right - 1]):
                is_pal[left][right] = True
                length = right - left + 1
                if length > best_length:
                    best_start = left
                    best_length = length
 
    return s[best_start:best_start + best_length]

The backward left loop makes the inner interval available before the outer interval asks for it.

Time O(n²) because each interval is processed once. Space O(n²) for the DP table.

Expand around centers — grow only valid palindromes

Every palindrome grows from a midpoint. Try each character for odd lengths and each gap for even lengths. Once a pair differs, no wider palindrome can survive at that center.

def longest_palindrome(s: str) -> str:
    best_start = 0
    best_length = 1
 
    def expand(left: int, right: int) -> None:
        nonlocal best_start, best_length
        while left >= 0 and right < len(s) and s[left] == s[right]:
            length = right - left + 1
            if length > best_length:
                best_start = left
                best_length = length
            left -= 1
            right += 1
 
    for center in range(len(s)):
        expand(center, center)
        expand(center, center + 1)
 
    return s[best_start:best_start + best_length]

There are 2n - 1 centers, and one center can expand O(n) positions in the worst case. The input guarantee removes tie handling: only one interval can achieve the maximum length.

Time O(n²) in the worst case. Space O(1) beyond the returned string.

LeetCode accepts either longest palindrome when there is a tie; our inputs guarantee a unique longest palindrome so the judge can compare one exact string.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrays: string

Expected

"bb"

Run: visible + custom · Submit: full suite