Longest Palindromic Substring

Hard · rating 1650 · strings, dp

Read a line. Print the length of its longest contiguous palindromic substring.

Constraints: 1 ≤ length ≤ 1000

Editorial

Longest Palindromic Substring is a popular string interview problem: find the longest contiguous substring that reads the same forwards and backwards.

Expand around center

Every palindrome has a center — a single character (odd length) or the gap between two characters (even length). There are 2n-1 centers; expand outward from each while the characters match, keeping the longest span.

def expand(l, r):
    while l >= 0 and r < n and s[l] == s[r]:
        l -= 1; r += 1
    return r - l - 1  # length of the palindrome

Complexity

Time: O(n²), fast in practice. Manacher's algorithm achieves O(n) but is rarely needed in interviews. Space: O(1).

Open Longest Palindromic Substring in Code Arena →