Skip to main content

5. Longest Palindromic Substring

mediumAsked at Google

Find the longest palindromic substring in a given string. Google asks this to test whether you reach for the expand-around-center technique and can articulate why it's O(n^2) instead of the naive O(n^3).

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L3/L4 onsite reports cite this as a recurring medium.
  • Reddit r/cscareerquestions (2025-10)— Common Google interview question.

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

Enumerate every (i, j) and check if s[i..j] is a palindrome.

Time
O(n^3)
Space
O(1)
function longestPalindromeBrute(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; substring + reverse + compare is O(n) inside the n^2 loop. Mention but move on.

2. Expand around center (optimal whiteboard)

For each index, expand outward as long as characters match. Handle odd-length (single center) and even-length (between two chars) cases.

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 - l - 1];
  }
  for (let i = 0; i < s.length; i++) {
    const [s1, len1] = expand(i, i);
    const [s2, len2] = expand(i, i + 1);
    if (len1 > maxLen) { start = s1; maxLen = len1; }
    if (len2 > maxLen) { start = s2; maxLen = len2; }
  }
  return s.slice(start, start + maxLen);
}

Tradeoff: O(n^2) total because each center expansion is O(n) and we have 2n - 1 centers (n odd + n-1 even). O(1) extra space — beats the DP solution on memory.

Google-specific tips

Google interviewers grade this on the dual handling of odd and even palindromes. State out loud: 'For each index, I'm trying two centers — one at the character (odd-length) and one between this char and the next (even-length).' If you only handle odd, you miss palindromes like 'bb'.

Common mistakes

  • Only handling odd-length palindromes (missing even-length).
  • Off-by-one in the returned indices: after the expand loop, l and r are the indices that FAILED, so the palindrome is s[l+1..r-1].
  • Forgetting to update maxLen + start in the same condition block.

Follow-up questions

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

  • Manacher's algorithm in O(n) — Google rarely requires it but mention you know it exists.
  • Count palindromic substrings (LC 647).
  • What if you needed all palindromic substrings, not just the longest?

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 is expand-around-center O(n^2) and not O(n^3)?

Brute-force is O(n^3) because for each (i, j) pair you do O(n) work to check palindrome-ness. Expand-around-center amortizes the check INTO the expansion: each expansion step is O(1), and the total expansion across all centers is bounded by O(n^2).

Should I learn Manacher's for Google?

Probably not. Google interviewers accept O(n^2) for this problem. Only mention Manacher's if asked; don't burn time coding it under pressure.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →