Longest Palindromic Substring

MediumDynamic ProgrammingStringDynamic Programming

Problem

Given a string, find its longest contiguous run of characters that reads identically forward and backward. If several palindromic substrings share the maximum length, returning any one of them is acceptable.

Example. For "babad", both "bab" and "aba" are valid answers, each of length 3.

Key idea

Checking every substring directly is expensive: there are O(n²) substrings, and verifying each one costs another O(n), so brute force is cubic. The observation that avoids re-verifying from scratch is that a substring is a palindrome exactly when its two outer characters match and the substring left after trimming them away is itself a palindrome.

That recurrence turns the problem into a table: mark a span as a palindrome based on whether the shorter span left after removing its two ends was already marked one. Filling the table by increasing span length guarantees the shorter span an entry needs is already computed. The same insight applies without a full table by expanding outward from each possible center (every character, plus every gap between two adjacent characters for even-length palindromes) and growing the window while its ends keep matching; the widest successful expansion is the palindrome centered there.

Solution

function longestPalindrome(s: string): string {
  let bestStart = 0;
  let bestLength = 0;

  for (let center = 0; center < s.length; center++) {
    const oddLength = expandAroundCenter(s, center, center); // palindrome centered on this character
    if (oddLength > bestLength) {
      bestLength = oddLength;
      bestStart = center - Math.floor((oddLength - 1) / 2);
    }

    const evenLength = expandAroundCenter(s, center, center + 1); // palindrome centered in the gap after this character
    if (evenLength > bestLength) {
      bestLength = evenLength;
      bestStart = center - Math.floor(evenLength / 2) + 1;
    }
  }

  return s.slice(bestStart, bestStart + bestLength);
}

function expandAroundCenter(s: string, left: number, right: number): number {
  // grow outward while both ends stay in bounds and keep matching
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    left--;
    right++;
  }
  return right - left - 1; // width of the widest matching window
}

Complexity

  • Time: O(n²). Every pair of start and end positions is considered once, either as a table cell or as a center expansion bounded by the string length.
  • Space: O(n²) for the table version; O(1) for the center-expansion version, since it only tracks the current best window.

Watch out for

  • Even-length palindromes have no single middle character, so centers between characters must be checked as well as centers on characters.
  • Fill the table (or run expansions) in order of increasing length so that shorter, already-solved spans are available when longer spans need them.
  • Track the best span's boundaries as you go rather than rescanning the whole table at the end.

Pattern

This is the "trim from both ends and reuse the smaller answer" interval DP pattern, the same idea that powers Palindromic Substrings and other problems built around symmetric spans of a sequence.

Related questions