{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Longest Palindromic Substring – Solution & Complexity

Interview solutions
/
Longest Palindromic Substring

Solution Walkthrough

  1. Step 1: Choose an Approach

    • Checking every substring for being a palindrome is O(n^3).
    • The clean, interview-friendly optimum is to expand around every possible center in O(n^2) time and O(1) space.
    • A palindrome is fully described by its center, so we grow outward from each center and remember the longest match.

  2. Step 2: Expand Around a Center

    • From a center, move two pointers outward while the characters match and stay in bounds.
    • Return the start and end indices of the widest palindrome found for that center.
    def expand(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    # step back to the last matching pair
    return left + 1, right - 1

  3. Step 3: Track the Longest Over All Centers

    • There are 2n - 1 centers: one at each character (odd length) and one between each pair (even length).
    • For each center, expand and update the best (start, end) window whenever a longer palindrome is found.
    def longest_palindrome(s: str) -> str:
    if not s:
        return ""
    start, end = 0, 0
    for i in range(len(s)):
        for l, r in (expand(s, i, i), expand(s, i, i + 1)):
            if r - l > end - start:
                start, end = l, r
    return s[start:end + 1]

  4. Step 4: Final Complete Solution

    • Each of the 2n - 1 centers expands at most O(n) times, so the total time is O(n^2).
    • We only store a couple of indices, so the extra space is O(1).
    def longest_palindrome(s: str) -> str:
    if not s:
        return ""

    def expand(left: int, right: int) -> tuple[int, int]:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    start, end = 0, 0
    for i in range(len(s)):
        for l, r in (expand(i, i), expand(i, i + 1)):
            if r - l > end - start:
                start, end = l, r
    return s[start:end + 1]

FAQ

See also

Practice Longest Palindromic Substring online (run code in the browser)Decode Ways solution (medium)Edit Distance solution (hard)Longest Common Subsequence solution (medium)Longest Valid Parentheses solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?