Longest Palindromic Substring

medium

two-pointersstringdynamic-programming

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

A substring reads the same forwards and backwards. If several substrings tie for the longest, return any one of them — any valid longest palindrome is accepted, not one specific string.

Example

Input: s = "babad"

Output: "bab"

"aba" is also accepted — both are length-3 palindromes.

Constraints

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

Intuition

A first pass checks every substring directly: for each start index paired with each end index, scan inward from both ends to see whether that slice reads the same forwards and backwards, keeping the longest one found so far.

function longestPalindrome(s) {
  let best = '';
  // Try every possible start index.
  for (let i = 0; i < s.length; i++) {
    // Try every possible end index, from i itself out to the end of the string.
    for (let j = i; j < s.length; j++) {
      const candidate = s.slice(i, j + 1);
      // Check the whole candidate, character by character, for symmetry.
      let isPalindrome = true;
      for (let l = 0, r = candidate.length - 1; l < r; l++, r--) {
        if (candidate[l] !== candidate[r]) { isPalindrome = false; break; }
      }
      // A longer palindrome always wins, even over one found earlier.
      if (isPalindrome && candidate.length > best.length) best = candidate;
    }
  }
  return best;
}

Brute force — every substring, checked character by character: O(n³).

This is O(n³) — far more work than necessary. Can we do better?

Checking whether s[i..j] is a palindrome from scratch throws away the previous answer: if s[i+1..j-1] was already known to be (or not be) a palindrome, then s[i..j] is one iff s[i] === s[j] and that inner range already is — no re-scan required. That's the same overlapping-subproblems signature dynamic programming exists to eliminate; the classic route memoizes that inner-range question in a 2-D dp[i][j] table.

There's a cheaper way to ask the exact same question, though. Every palindrome has a center — a single character for odd length, or the gap between two characters for even length — and it's a palindrome precisely as long as expanding outward from that center hasn't failed yet. So instead of filling a table bottom-up, grow each of the 2n - 1 centers outward until the two ends stop matching. It visits the same 'is the inside a palindrome' work the table would, just without ever allocating it — the stored solution rolls the whole recurrence into two integer pointers, l and r, instead of an n × n grid.

Walking it through:

s = "abaxyzzyxf"

l↓r↓

l = 0 already at the left edge → expand(0, 0) stops at length 1

Center 0 is the string's very first character, so there's nowhere further left to expand — the boundary check `l >= 0` cuts it short.

l↓

r↓

s[0] = 'a' = s[2] → expand(1, 1) reaches length 3

Centered on index 1, 'aba' matches once outward before hitting the string's start — new best: 'aba'.

l↓

r↓

s[2] = 'a' ≠ s[4] = 'y' → stop, length 1

Not every center pays off — the 'x' at index 3 can't extend either direction, so it's discarded without disturbing the best found so far.

l↓

r↓

s[5] = 'z' = s[6] → seed an even center

Between indices 5 and 6 the two z's match — an even-length palindrome starts growing from the gap.

l↓

r↓

y = y, then x = x → expand(5, 6) reaches length 6

The match survives two more expansions — new best: 'xyzzyx', overtaking 'aba'.

l↓

r↓

s[2] = 'a' ≠ s[9] = 'f' → stop expanding

The scan finishes without finding anything longer; 'xyzzyx' (indices 3-8) is returned as the longest palindromic substring.

Optimization

Expand around center

Every palindrome has a center — a single character (odd length) or a gap between two characters (even length). There are 2n - 1 such centers. From each, expand outward while the characters match; the widest span seen is the answer.

O(n²) time, O(1) space.

function longestPalindrome(s) {
  // Fewer than 2 characters is trivially its own longest palindrome.
  if (s.length < 2) return s;
  let start = 0;
  let end = 0;
  // Grow outward from a center (l, r) while the ends still match; return the palindrome's length.
  const expand = (l, r) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
    return r - l - 1;
  };
  // Every palindrome has a center: a single character (odd length) or a gap between two (even length).
  for (let i = 0; i < s.length; i++) {
    // Try both kinds of center rooted at i, and keep whichever grows further.
    const len = Math.max(expand(i, i), expand(i, i + 1));
    // A strictly longer palindrome replaces the current best; ties keep the earlier one.
    if (len > end - start + 1) {
      start = i - Math.floor((len - 1) / 2);
      end = i + Math.floor(len / 2);
    }
  }
  return s.slice(start, end + 1);
}

Complexity analysis

Time complexity: O(n²). Here's why:

The outer loop runs once per index i (n iterations), trying both an odd center (i, i) and an even center (i, i + 1).
Each expand call can walk up to O(n) characters outward before it hits a mismatch or a string boundary — a string of all the same character never stops early.

So the total work is n centers × O(n) expansion each = O(n²) — down from the brute force's O(n³), since checking a center's palindrome-ness no longer means re-scanning every candidate substring from scratch.

Space complexity: O(1). Here's why:

Only a handful of scalar variables are kept — start, end, and the l/r pair inside expand — never a 2-D dp table or a list of candidate substrings.
expand is a plain loop, not a recursive call, so there's no call stack to add on top.

The final s.slice(start, end + 1) allocates the answer string, but that's the output, not extra working space — so the algorithm itself runs in O(1).

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
s = "q"	"q"	Single character — trivially its own longest palindrome.
s = "xy"	"x"	Two distinct characters — no palindrome longer than 1 exists; the strict `>` update never fires, so the reference keeps the very first character.
s = "eeee"	"eeee"	Every character the same — expanding from the middle never fails until it runs off both edges, so the whole string wins.
s = "zaza"	"zaz"	Two overlapping length-3 palindromes tie ('zaz' at indices 0-2, 'aza' at indices 1-3); the strict `>` comparison keeps whichever was found first.
s = "abcddcbef"	"bcddcb"	The longest palindrome sits away from either edge and is even-length — exercises a center between two different repeated characters.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor