Skip to main content

33. Longest Palindromic Substring

mediumAsked at Snowflake

Find 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 Alex Chen, 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 <= 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. 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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →