33. Longest Palindromic Substring
mediumAsked at PlaidReturn the longest contiguous palindrome inside a string — the classic home of the expand-around-center technique and its sneaky requirement to handle BOTH odd and even centers. Plaid candidates report it as a string-fluency check that precedes harder canonicalization work (think normalizing messy merchant-name strings), with the grading weight on clean center-handling rather than on knowing the exotic O(n) algorithm.
By Sam K., 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. A substring must be contiguous (unlike a subsequence), and when several palindromes tie for the maximum length, returning any one of them is accepted.
Constraints
1 <= s.length <= 1000s consist of only digits and English letters.At n = 1000, O(n^2) expansion runs in well under a millisecond — the O(n^3) brute force is the only approach the bound actually rules out.
Examples
Example 1
s = "babad""bab"Explanation: "aba" is also a valid answer.
Example 2
s = "cbbd""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: every one of the O(n^2) substrings pays an O(n) palindrome check, and the slice-and-reverse inside the loop allocates on every iteration. State it as the naive baseline in one sentence and pivot to centers — lingering here reads as not seeing the structure palindromes share.
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 candidates report the grading hinges on handling both odd and even centers through ONE expand helper called twice — writing two near-identical loops is the visible amateur tell. Walk a worked example out loud ('for cbbd, the even center between the two b's is the winner') because the even case is exactly what untested code misses. Mention Manacher's O(n) algorithm by name as a stretch goal but only implement it if explicitly asked — at n <= 1000 it is pure overkill, and saying so is itself a judgment signal.
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.
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.
Why are there exactly 2n - 1 centers?
Each of the n characters is a potential odd-length center, and each of the n - 1 gaps between adjacent characters is a potential even-length center. Every palindrome maps to exactly one of these, so checking all 2n - 1 covers every case.