Skip to main content

33. Longest Palindromic Substring

mediumAsked at Salesforce

Return the longest palindromic substring in s. Salesforce uses this to test the expand-around-center pattern — they expect a clean O(n^2) solution.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Asked on Salesforce backend onsites to gauge two-pointer fluency.
  • LeetCode Discuss (2025)— Manacher's algorithm rarely required; expand-around-center suffices.

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

Check every substring; track the longest palindrome.

Time
O(n^3)
Space
O(1)
function longestPalindrome(s) {
  const isPal = (l, r) => {
    while (l < r) { if (s[l] !== s[r]) return false; l++; r--; }
    return true;
  };
  let best = '';
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      if (isPal(i, j) && j - i + 1 > best.length) best = s.slice(i, j + 1);
    }
  }
  return best;
}

Tradeoff: Cubic. Salesforce will push to O(n^2).

2. Expand around center

For each index (and each gap), expand outward while characters match. 2n - 1 centers total.

Time
O(n^2)
Space
O(1)
function longestPalindrome(s) {
  let start = 0, maxLen = 1;
  function expand(l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
    return [l + 1, r - l - 1];
  }
  for (let i = 0; i < s.length; i++) {
    const [s1, len1] = expand(i, i);
    const [s2, len2] = expand(i, i + 1);
    if (len1 > maxLen) { start = s1; maxLen = len1; }
    if (len2 > maxLen) { start = s2; maxLen = len2; }
  }
  return s.slice(start, start + maxLen);
}

Tradeoff: O(n^2) time, O(1) space. Handles odd and even palindromes by trying both center types.

Salesforce-specific tips

Salesforce grades on whether you handle BOTH odd-length (center is one char) and even-length (center is two chars) palindromes. Missing the even case is the #1 disqualifier. Bonus signal: mention Manacher's algorithm for O(n) — they don't expect you to code it but knowing it exists is bonus.

Common mistakes

  • Only handling odd-length palindromes — misses 'bb' in 'cbbd'.
  • Returning the length instead of the substring — read the problem.
  • Using s.slice in the inner expand — turns O(n^2) into O(n^3).

Follow-up questions

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

  • Manacher's algorithm — O(n) time.
  • Palindromic Substrings (LC 647) — count, not find.
  • Longest Palindromic Subsequence (LC 516) — DP, not contiguous.

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 expand around 2n - 1 centers?

n single-char centers (for odd palindromes) + n-1 gaps (for even palindromes) = 2n - 1 total centers. Each gives the maximal palindrome with that center.

What's the recurrence in the DP solution?

dp[i][j] = true iff s[i] == s[j] AND dp[i+1][j-1]. O(n^2) time and space; same time complexity as expand-around-center but more memory.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →