Skip to main content

33. Longest Palindromic Substring

mediumAsked at Reddit

Find the longest palindromic substring of a string. Reddit asks this to test expand-around-centers — the same pattern used in their similarity-detection between post titles (mirror-image substring matching for spam detection).

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, used to gauge string-DP comfort.

Problem

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

Constraints

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

Examples

Example 1

Input
s = "babad"
Output
"bab"

Explanation: "aba" is also valid.

Example 2

Input
s = "cbbd"
Output
"bb"

Approaches

1. Brute force all substrings

Check every substring for palindrome.

Time
O(n^3)
Space
O(1)
function longestPalindrome(s) {
  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: Cubic. Mention as the anti-pattern.

2. Expand around centers (optimal)

For each i in [0, n), expand around (i, i) for odd-length and (i, i+1) for even-length. Track max.

Time
O(n^2)
Space
O(1)
function longestPalindrome(s) {
  if (!s) return '';
  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++) {
    const [l1, r1] = expand(i, i);
    const [l2, r2] = expand(i, i + 1);
    if (r1 - l1 > end - start) { start = l1; end = r1; }
    if (r2 - l2 > end - start) { start = l2; end = r2; }
  }
  return s.slice(start, end + 1);
}

Tradeoff: O(n^2) time, O(1) space. Manacher's algorithm gets to O(n) but is rarely required.

Reddit-specific tips

Reddit interviewers want expand-around-centers. Bonus signal: mention Manacher's O(n) and that you'd reach for it if n > 10^4 — but for n ≤ 1000, the simpler O(n^2) is preferred.

Common mistakes

  • Only checking odd-length palindromes (miss 'bb').
  • Returning the length instead of the substring.
  • Off-by-one in slice (must be end + 1 not end).

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

  • Manacher's algorithm — O(n).
  • Palindromic Substrings (LC 647) — count instead of longest.
  • Longest palindromic subsequence (LC 516).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why two expand calls per center?

Odd-length palindromes (aba) center on a char; even-length (abba) center between chars. Both must be checked.

Is DP also a valid approach?

Yes — 2D dp[i][j] = is s[i..j] a palindrome. O(n^2) time and space. Expand-centers wins on space.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →