Skip to main content

33. Longest Palindromic Substring

mediumAsked at Datadog

Find the longest palindromic substring. Datadog asks this for the expand-around-center pattern — O(n^2) time with O(1) space, a sweet spot for streaming validators that can't afford O(n) extra memory.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — expand-around-center expected.
  • LeetCode Discuss (2025-10)— Datadog tagged.

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" or "aba"

Example 2

Input
s = "cbbd"
Output
"bb"

Approaches

1. DP table

dp[i][j] = is s[i..j] a palindrome. Fill bottom-up by length.

Time
O(n^2)
Space
O(n^2)
function longestPalindrome(s) {
  const n = s.length;
  const dp = Array.from({length: n}, () => new Array(n).fill(false));
  let bestStart = 0, bestLen = 1;
  for (let i = 0; i < n; i++) dp[i][i] = true;
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len <= n; i++) {
      const j = i + len - 1;
      if (s[i] === s[j] && (len === 2 || dp[i + 1][j - 1])) {
        dp[i][j] = true;
        if (len > bestLen) { bestLen = len; bestStart = i; }
      }
    }
  }
  return s.substring(bestStart, bestStart + bestLen);
}

Tradeoff: O(n^2) memory. Datadog will push for O(1) extra space.

2. Expand around center (optimal)

Each of the 2n-1 centers (n odd + n-1 even). Expand outward while s[lo] === s[hi]. Track the longest.

Time
O(n^2)
Space
O(1)
function longestPalindrome(s) {
  let bestStart = 0, bestLen = 0;
  function expand(lo, hi) {
    while (lo >= 0 && hi < s.length && s[lo] === s[hi]) {
      lo--; hi++;
    }
    const len = hi - lo - 1;
    if (len > bestLen) { bestLen = len; bestStart = lo + 1; }
  }
  for (let i = 0; i < s.length; i++) {
    expand(i, i);     // odd-length center
    expand(i, i + 1); // even-length center
  }
  return s.substring(bestStart, bestStart + bestLen);
}

Tradeoff: O(1) extra space. Datadog-canonical: the same expand-around-center pattern they use to find palindromic patterns in log streams without backtracking.

Datadog-specific tips

Datadog wants the expand-around-center, not the DP table. Mention Manacher's algorithm as the O(n) optimum but don't write it under time pressure — it's bug-prone. Articulate the odd/even center pairing before coding.

Common mistakes

  • Iterating only odd centers — misses even-length palindromes like 'abba'.
  • Off-by-one in the length calculation — hi - lo - 1 is correct because the while loop exits with mismatched lo and hi.
  • Tracking only the length, not the start index — can't return the substring.

Follow-up questions

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

  • Palindromic Substrings (LC 647) — count them all.
  • Longest Palindromic Subsequence (LC 516) — different DP.
  • Manacher's algorithm — O(n) optimum, advanced.

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 index?

Odd-length palindromes have a single center character; even-length have a center pair. You need both to cover all cases.

Why is the answer length hi - lo - 1?

The while loop exits when s[lo] !== s[hi] or out-of-bounds, so the actual palindrome is s[lo+1..hi-1] of length (hi-1) - (lo+1) + 1 = hi - lo - 1.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →