33. Longest Palindromic Substring
mediumAsked at SnowflakeFind the longest palindromic substring of a string. Snowflake asks this to test the 'expand-around-center' insight — and how to avoid the O(n^2) memory cost of DP when streaming through a column would be cheaper.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Snowflake loops.
- Glassdoor (2025-Q4)— Snowflake new-grad onsite, paired with DP-to-O(1)-space follow-up.
- LeetCode Discuss (2025-10)— Reported at Snowflake SDE-I screens.
Problem
Given a string s, return the longest palindromic substring in s.
Constraints
1 <= s.length <= 1000s consist of only digits and English letters.
Examples
Example 1
s = "babad""bab"Explanation: "aba" is also a valid answer.
Example 2
s = "cbbd""bb"Approaches
1. Brute force every substring
For every (i, j), check 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. Mention only to reject.
2. Expand around center (optimal for n <= 1000)
For each index, try both odd-length and even-length expansion. O(n^2) time but O(1) space.
- 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++; }
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 + 1 > maxLen) { start = l1; maxLen = r1 - l1 + 1; }
if (r2 - l2 + 1 > maxLen) { start = l2; maxLen = r2 - l2 + 1; }
}
return s.slice(start, start + maxLen);
}Tradeoff: n^2 time, O(1) space. The center-expansion trick beats DP's O(n^2) space.
Snowflake-specific tips
Snowflake interviewers grade this on whether you reach expand-around-center after dismissing DP (DP costs O(n^2) memory; center-expansion doesn't). Bonus signal: mention Manacher's algorithm (O(n)) as the asymptotic optimum, with the trade-off that it's significantly harder to write under interview pressure.
Common mistakes
- Doing only odd-length expansion — misses even-length palindromes like 'bb'.
- Returning the length instead of the substring.
- Off-by-one when reconstructing the substring boundaries.
Follow-up questions
An interviewer at Snowflake may pivot to one of these next:
- Manacher's algorithm — O(n).
- Count palindromic substrings (LC 647).
- Palindromic Substrings with DP.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why two expansions per center?
Palindromes can have odd length (one-char center) or even length (two-char center). You need both kinds of expansion to find all candidates.
Why is O(n^2) acceptable here?
n <= 1000 so n^2 = 10^6 — well within budget. Manacher's O(n) is provably better asymptotically but isn't needed at this size.