Longest Palindromic Substring

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Given a string, return its longest contiguous substring that reads the same forwards and backwards. If several have the same maximum length, any one of them is accepted.

    The standard answer, "expand around every centre", is short, needs O(1) extra space and is what most interviewers expect. The 2D DP and Manacher's algorithm are good things to mention. Original problem: LeetCode 5.

    Example

    "anana" is the longest palindrome in "banana" (odd length); "abba" in "xabbay" has even length.
    "anana" is the longest palindrome in "banana" (odd length); "abba" in "xabbay" has even length.
    Input:  "banana"
    Output: "anana"
    Input:  "xabbay"
    Output: "abba"
    Input:  "q"
    Output: "q"

    Constraints (assumed)

    • 1 ≤ length ≤ 1,000.
    • Letters and digits only.

    What this question tests

    • Using the structure of a palindrome (symmetry around a centre) instead of checking every substring.
    • Handling odd and even lengths in one clean loop.
    • Index arithmetic: turning the final lo/hi back into the right substring.

    Questions to ask first

    1. Substring or subsequence? (Substring: contiguous. Longest palindromic subsequence is a different DP.)
    2. If there are ties, which one? (Here: any.)
    3. Case sensitive? Spaces and punctuation? (Here: compare characters as they are.)
    4. How long can the string be? O(n²) is fine for 1,000; ask before reaching for Manacher.