Skip to main content

16. Longest Palindromic Substring

mediumAsked at Adyen

Return the longest palindromic substring in the given string.

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

Problem

Given a string s, return the longest palindromic substring in s.

Constraints

  • 1 <= s.length <= 1000
  • s consists of 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 for palindrome property.

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].reverse().join('') && sub.length > best.length) best = sub;
}
return best;

Tradeoff:

2. Expand around center

Expand from every center (odd and even) and track the best.

Time
O(n^2)
Space
O(1)
function longestPalindrome(s) {
  let lo = 0, hi = 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 [a, b] of [expand(i, i), expand(i, i+1)]) {
      if (b - a > hi - lo) { lo = a; hi = b; }
    }
  }
  return s.slice(lo, hi + 1);
}

Tradeoff:

Adyen-specific tips

Adyen graders look for the dual odd/even center expansion — sloppy candidates only handle one and lose the trailing-pair case that mirrors symmetric currency-code pairings.

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 Adyen interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →