Longest Palindromic Substring

Tags

Longest Palindromic Substring

Category

Strings

Difficulty

Medium

Problem Statement

Given a string, find and return the longest substring that is a palindrome. If there are multiple palindromic substrings of the same maximum length, return the first one encountered (leftmost).

Intuition

Every palindrome expands symmetrically around its center. A palindrome of odd length has a single center character, while a palindrome of even length has a center between two characters. By treating each index (and each pair of adjacent indices) as a potential center and expanding outward as long as characters match, we can find the longest palindrome efficiently without needing extra space for a DP table.

Approach

  1. Initialize a variable to track the longest palindrome found (start index and length).
  2. For each index i in the string:
    • Expand around center (i, i) for odd-length palindromes.
    • Expand around center (i, i + 1) for even-length palindromes.
  3. For each expansion, move outward while characters at both ends match and indices are in bounds.
  4. If the current palindrome is longer than the best found so far, update the best.
  5. Return the substring corresponding to the longest palindrome.

Pseudocode

function longestPalindromicSubstring(string):
    bestStart = 0
    bestLength = 1

    for i from 0 to length(string) - 1:
        // Odd-length palindromes
        oddPalin = expandAroundCenter(string, i, i)
        if length(oddPalin) > bestLength:
            bestStart = start(oddPalin)
            bestLength = length(oddPalin)

        // Even-length palindromes
        evenPalin = expandAroundCenter(string, i, i + 1)
        if length(evenPalin) > bestLength:
            bestStart = start(evenPalin)
            bestLength = length(evenPalin)

    return substring(string, bestStart, bestStart + bestLength)

function expandAroundCenter(string, left, right):
    while left >= 0 and right < length(string) and string[left] == string[right]:
        left = left - 1
        right = right + 1
    return (left + 1, right - left - 1)  // start index and length

Time & Space Complexity

  • Time: O(n^2) where n is the length of the string. There are 2n - 1 possible centers and each expansion can take up to O(n) time.
  • Space: O(1) if we track indices and extract the substring at the end. O(n) for the returned substring itself.

Key Insights

  • The expand-around-center technique is simpler and more space-efficient than the dynamic programming approach, which requires an O(n^2) table.
  • There are 2n - 1 possible centers (n for odd-length, n - 1 for even-length palindromes).
  • Manacher's algorithm can solve this in O(n) time but is significantly more complex to implement.
  • Expanding from the center naturally finds the longest palindrome at each position.

Edge Cases

  • Single character string: the entire string is the answer.
  • String with no palindromic substring longer than 1: return the first character.
  • Entire string is a palindrome: the expansion from the middle center will find it.
  • Multiple palindromes of the same maximum length: return the leftmost one since we iterate left to right.
  • Even-length palindromes (e.g., "abba"): caught by the even-center expansion.
  • String of all identical characters (e.g., "aaaa"): the entire string is the palindrome.

Linked mentions