Skip to main content

17. Longest Palindromic Substring

mediumAsked at Yelp

Find the longest palindromic substring in a string — Yelp uses expand-from-center to test a candidate's ability to find structural patterns inside long review text bodies.

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

Problem

Given a string s, return the longest palindromic substring in s. Substrings must be contiguous.

Constraints

  • 1 <= s.length <= 1000
  • s consists of only digits and English letters

Examples

Example 1

Input
s = "babad"
Output
"bab"

Example 2

Input
s = "cbbd"
Output
"bb"

Approaches

1. Brute force

Check every substring against its reverse.

Time
O(n^3)
Space
O(1)
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:

2. Expand from each center

Treat each index (and each adjacent pair) as a potential palindrome center and expand outward while characters match.

Time
O(n^2)
Space
O(1)
function longestPalindrome(s) {
  let start = 0, end = 0;
  const 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++) {
    for (const [l, r] of [expand(i, i), expand(i, i + 1)]) {
      if (r - l > end - start) { start = l; end = r; }
    }
  }
  return s.slice(start, end + 1);
}

Tradeoff:

Yelp-specific tips

Yelp interviewers will pivot to review ranking — be ready to discuss how palindrome detection generalizes to spotting unnaturally symmetric phrasing that hints at templated spam reviews.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →