33. Longest Palindromic Substring

Q: Why r - l - 1 for length?

The loop exits when s[l] !== s[r] (or out of bounds). So the actual palindrome is s[l+1..r-1], length = r - l - 1.

Q: Even and odd?

Odd-length palindromes have a single character center; even-length have two. Try both for each starting index.

mediumAsked at Workday

Find the longest palindromic substring of a given string. Workday uses this as a DP vs expand-around-center decision point — both are valid; choosing the right one is the test.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Workday loops.

Glassdoor (2025-Q4)— Workday SDE2 phone screen.

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 a valid answer.

Example 2

Input

s = "cbbd"

Output

"bb"

Approaches

1. Brute force all substrings

Check each substring for palindrome.

Time: O(n^3)
Space: O(1)

// O(n^2) substrings * O(n) palindrome check

Tradeoff: Cubic. Slow even at n=1000.

2. Expand around each center

For each index, expand around it (odd-length) and around (i, i+1) (even-length). Track longest.

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

function longestPalindrome(s) {
  if (!s) return '';
  let start = 0, maxLen = 1;
  function expand(l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
    const len = r - l - 1;
    if (len > maxLen) { maxLen = len; start = l + 1; }
  }
  for (let i = 0; i < s.length; i++) {
    expand(i, i);
    expand(i, i + 1);
  }
  return s.slice(start, start + maxLen);
}

Tradeoff: O(n^2) time, O(1) space. Cleaner than the DP table and same complexity.

Workday-specific tips

Workday accepts either DP or expand-around-center, but the expand version is cleaner and uses O(1) space. State both even-length and odd-length cases explicitly. Manacher's is overkill — they don't expect it.

Common mistakes

Only doing odd-length (expand from single center) — misses 'bb'.
Returning the length instead of the substring.
Off-by-one when computing r - l - 1 (because the loop exits after a mismatch).

Follow-up questions

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

Palindromic Substrings (LC 647) — count them all.
Longest Palindromic Subsequence (LC 516) — non-contiguous.
Manacher's algorithm — O(n).

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 r - l - 1 for length?

The loop exits when s[l] !== s[r] (or out of bounds). So the actual palindrome is s[l+1..r-1], length = r - l - 1.

Even and odd?

Odd-length palindromes have a single character center; even-length have two. Try both for each starting index.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →