Frontend Beauty
ESC

Type to search the knowledge base.

Longest Palindromic Substring

Longest palindromic substring — expand around centers O(n²), DP table alternative, and Manacher mention for O(n).

intermediate3 min read
  • dsa
  • dp
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

Return the longest palindromic substring of s. Any one is fine if ties.

"babad" → "bab" or "aba"
"cbbd" → "bb"

Brute

Check every s[i..j] for palindrome. O(n³) or O(n²) with better checks.

function longestPalindromeBrute(s: string): string {
  let best = "";
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      if (j - i + 1 > best.length && isPal(s, i, j)) best = s.slice(i, j + 1);
    }
  }
  return best;
}

function isPal(s: string, i: number, j: number): boolean {
  while (i < j) {
    if (s[i] !== s[j]) return false;
    i++;
    j--;
  }
  return true;
}
Time O(n³)
Space O(1)

Expand around centers (preferred)

Every palindrome mirrors around a center. Centers are each index (odd length) and each gap between indices (even length). Expand while characters match.

function longestPalindrome(s: string): string {
  if (!s) return "";
  let start = 0;
  let end = 0;

  const expand = (l: number, r: number) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      l--;
      r++;
    }
    // after fail, window is (l+1)..(r-1)
    if (r - l - 1 > end - start + 1) {
      start = l + 1;
      end = r - 1;
    }
  };

  for (let i = 0; i < s.length; i++) {
    expand(i, i);     // odd
    expand(i, i + 1); // even
  }
  return s.slice(start, end + 1);
}
Time O(n²)
Space O(1)

Walk "cbbd"

Centers… at gap between two bs expand → "bb", longest.

DP table (also O(n²))

dp[i][j] = true if s[i..j] palindrome.
dp[i][j] = (s[i]===s[j]) && (j-i<2 || dp[i+1][j-1]).

function longestPalindromeDp(s: string): string {
  const n = s.length;
  if (n < 2) return s;
  const dp: boolean[][] = Array.from({ length: n }, () => Array(n).fill(false));
  let start = 0;
  let maxLen = 1;

  for (let i = 0; i < n; i++) dp[i][i] = true;

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      if (s[i] === s[j] && (len === 2 || dp[i + 1][j - 1])) {
        dp[i][j] = true;
        if (len > maxLen) {
          maxLen = len;
          start = i;
        }
      }
    }
  }
  return s.slice(start, start + maxLen);
}
Time O(n²)
Space O(n²)

Manacher’s algorithm

True O(n) with transformed string and radius array. Rarely required; name it if they ask for better than n².

Edge cases

  • Empty / single char
  • Entire string palindrome
  • All same characters
  • Even vs odd lengths

Common mistakes

  • Only expanding odd centers (miss "bb")
  • Returning length instead of substring
  • Off-by-one after expand loop

Interview delivery

  1. Substring not subsequence.
  2. Expand centers O(n²)/O(1).
  3. Code both odd and even.
  4. Mention DP / Manacher.
  5. Trace even case.

Further reading