Skip to main content

33. Longest Palindromic Substring

mediumAsked at Vercel

Find the longest palindromic substring. Vercel asks this for the expand-around-center technique, which is the cleanest O(n^2) approach and shows up in their text-diff and serverless cold-start analysis.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel onsite; expand-around-center expected.
  • Blind (2026-Q1)— Listed in Vercel platform screen.

Problem

Given a string s, return the longest palindromic substring in s.

Constraints

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.

Examples

Example 1

Input
s = "babad"
Output
"bab"

Explanation: "aba" is also a valid answer.

Example 2

Input
s = "cbbd"
Output
"bb"

Approaches

1. DP table

dp[i][j] = whether s[i..j] is a palindrome; fill bottom-up.

Time
O(n^2)
Space
O(n^2)
function longestPalindrome(s) {
  const n = s.length;
  const dp = Array.from({length: n}, () => new Array(n).fill(false));
  let start = 0, 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 <= 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) { start = i; maxLen = len; }
      }
    }
  }
  return s.substring(start, start + maxLen);
}

Tradeoff: O(n^2) time and space. Verbose; the expand-around-center is preferred.

2. Expand around center (optimal for interview)

Every palindrome has a center (odd) or two centers (even). For each of the 2n-1 possible centers, expand outward while characters match.

Time
O(n^2)
Space
O(1)
function longestPalindrome(s) {
  let start = 0, end = 0;
  function expand(l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
    return [l + 1, r - 1];
  }
  for (let i = 0; i < s.length; i++) {
    const [l1, r1] = expand(i, i);
    const [l2, r2] = expand(i, i + 1);
    if (r1 - l1 > end - start) { start = l1; end = r1; }
    if (r2 - l2 > end - start) { start = l2; end = r2; }
  }
  return s.substring(start, end + 1);
}

Tradeoff: O(1) extra space. The two expansions per center (odd and even palindromes) handle both shapes uniformly. Manacher's gives O(n) but is rarely expected in interviews.

Vercel-specific tips

Vercel grades expand-around-center; the DP version is fine but more code. Bonus signal: mentioning Manacher's algorithm for O(n) (without coding) and handling both odd and even palindromes by calling expand with (i, i) and (i, i+1).

Common mistakes

  • Only checking odd-length palindromes — misses even ones like 'bb'.
  • Off-by-one in the post-loop boundaries — l+1, r-1 are the actual palindrome bounds.
  • Mutating the result with substring vs slice — both work but be consistent.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Manacher's algorithm — O(n).
  • Count all palindromic substrings (LC 647).
  • Palindromic substrings starting at index 0 (LC 5 variant).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why two expansions per center?

Odd palindromes have one middle character (expand from i, i). Even palindromes have two middle characters (expand from i, i+1). Without both, you miss half the candidates.

Is Manacher's worth learning?

For interviews at Vercel: no, expand-around-center is the expected answer. For competitive programming, yes. The O(n^2) is fast enough for n=1000.

Practice these live with InterviewChamp.AI

Drill Longest Palindromic Substring and other Vercel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →