Skip to main content

33. Longest Palindromic Substring

mediumAsked at Plaid

Find the longest palindromic substring. Plaid asks this as a 'expand around center' fluency check before harder string-canonicalization problems on merchant names.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • LeetCode Discuss (2026)— Plaid SWE II OA.
  • Glassdoor (2025)— Plaid string-handling 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. Check every substring

Try every (i, j) pair, check if palindrome.

Time
O(n^3)
Space
O(1)
function longestPalindrome(s) {
  let best = '';
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      const sub = s.slice(i, j + 1);
      if (sub === sub.split('').reverse().join('') && sub.length > best.length) best = sub;
    }
  }
  return best;
}

Tradeoff: Cubic. Don't ship for n > 500.

2. Expand around each center

Each palindrome has a center (single char or between two chars). For each of 2n-1 centers, expand outward as long as characters match.

Time
O(n^2)
Space
O(1)
function longestPalindrome(s) {
  let start = 0, maxLen = 0;
  function expand(l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
    if (r - l - 1 > maxLen) { maxLen = r - l - 1; start = l + 1; }
  }
  for (let i = 0; i < s.length; i++) {
    expand(i, i);       // odd-length center
    expand(i, i + 1);   // even-length center
  }
  return s.slice(start, start + maxLen);
}

Tradeoff: O(n^2) but each expansion is O(1) amortized in the best case. The two-center expansion handles both odd and even palindromes.

Plaid-specific tips

Plaid grades this on whether you handle both odd and even centers without writing duplicate code. Bonus signal: mention Manacher's O(n) algorithm by name as a stretch, but only ship it if explicitly asked — it's overkill for n <= 1000.

Common mistakes

  • Only handling odd-length palindromes — misses 'bb' style cases.
  • Off-by-one in the start/length math after expansion — easy to get the slice indices wrong.
  • Trying to use DP (O(n^2) space) — fine but unnecessarily allocates.

Follow-up questions

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

  • Manacher's algorithm — O(n).
  • Count all palindromic substrings (LC 647) — same expansion, count instead of track.
  • Longest palindromic subsequence (LC 516) — different problem, O(n^2) DP.

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?

An odd-length palindrome's center is a single character; an even-length palindrome's center is between two characters. We need both.

Why not DP?

DP is O(n^2) time AND O(n^2) space. Expand-around-center is the same time but O(1) space. Identical asymptotic, better constants.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →