Longest Palindromic Substring

Examples

Input: s = "babad"
Output: "bab"

"aba" is also a valid answer — both have length 3.

Input: s = "cbbd"
Output: "bb"

The longest palindrome is "bb"; single letters like "c" or "d" are shorter.

Input: s = "a"
Output: "a"

Constraints

• 1 <= s.length <= 1000

• s consists of only lowercase English letters

Approach

A palindrome is defined by its center: everything mirrors outward from the middle. That means instead of checking every one of the roughly n²/2 substrings independently, you can pick every possible center — each single character (for odd-length palindromes) and every gap between two characters (for even-length palindromes) — and grow outward from it as far as the mirroring holds.

For each of the 2n - 1 centers, expanding outward stops the moment the two sides stop matching, so the whole scan stays quadratic instead of cubic. Track the longest palindrome seen as you go.

Solutions

Brute Force — Check Every Substring

Generate every possible substring, check whether each one is a palindrome by comparing it to its own reverse, and keep the longest one found.

function longestPalindrome(s) {
  function isPalindrome(str) {
    let left = 0;
    let right = str.length - 1;
    while (left < right) {
      if (str[left] !== str[right]) return false;
      left++;
      right--;
    }
    return true;
  }

  let longest = "";
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      const candidate = s.slice(i, j + 1);
      if (candidate.length > longest.length && isPalindrome(candidate)) {
        longest = candidate;
      }
    }
  }
  return longest;
}

Time: O(n^3) — O(n^2) substrings, each checked in O(n) · Space: O(1) extra, ignoring the substrings themselves

Optimal — Expand Around Center

Treat every character (and every gap between two characters) as a potential center of a palindrome, and grow outward from it while both sides keep matching. Track the widest palindrome found across all centers.

function longestPalindrome(s) {
  let start = 0;
  let maxLength = 1;

  function expand(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    // left/right overshot by one step; the real palindrome is (left+1 .. right-1)
    const length = right - left - 1;
    if (length > maxLength) {
      maxLength = length;
      start = left + 1;
    }
  }

  for (let i = 0; i < s.length; i++) {
    expand(i, i);       // odd-length palindromes centered on i
    expand(i, i + 1);   // even-length palindromes centered between i and i+1
  }

  return s.slice(start, start + maxLength);
}

Time: O(n^2) · Space: O(1) extra