Longest palindromic substring

Medium TimeO(n²) SpaceO(1)

Given a string s, return the longest stretch of adjacent characters in it that reads the same backwards as forwards. The characters have to be contiguous. A stretch may be of odd length, sitting on a middle character, or of even length, sitting on the gap between two. Any single character qualifies, so the answer is never empty for a non-empty s, and where two stretches tie for longest either one is a correct answer.

Examples

Example 1

Input
s = "babad"
Output
"bab"
"bab" and "aba" are both three characters long, and "bab" is the one reached first.

Example 2

Input
s = "cbbd"
Output
"bb"
The answer sits on the gap between two characters rather than on one, so it has an even length.

The Code

function longestPalindrome(s) {
  let best = "";
  function expand(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    return s.slice(left + 1, right);
  }
  for (let i = 0; i < s.length; i++) {
    const odd = expand(i, i);
    if (odd.length > best.length) best = odd;
    const even = expand(i, i + 1);
    if (even.length > best.length) best = even;
  }
  return best;
}
longestPalindrome("babad");
Done

The first 27 calls, of 29. This one does not fit on a page.

Step through longestPalindrome("babad") call by call

More like this

All strings examples (13) →