33. Longest Palindromic Substring
mediumAsked at SalesforceAmong all substrings of s, find the longest one that reads the same forwards and backwards. Salesforce candidates report this medium as an expand-around-center fluency check where the even-length case is the silent killer: every string of length n hides 2n - 1 possible palindrome centers, and forgetting the n - 1 between-character centers (the 'bb' in 'cbbd') is the single most common disqualifier on an otherwise clean solution.
By Sam K., 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. The substring must be contiguous, and when multiple palindromes tie at the maximum length, any one of them is an accepted answer.
Constraints
1 <= s.length <= 1000s consist of only digits and English letters.A single character is always a palindrome, so the answer length is at least 1 — no empty-result handling needed.
Examples
Example 1
s = "babad""bab"Explanation: "aba" is also a valid answer.
Example 2
s = "cbbd""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 — every one of the O(n^2) substrings pays its own O(n) palindrome check. Fine to sketch as the definition of correctness, but the interviewer's next sentence will be a push toward reusing work across overlapping checks, which is exactly what centers do.
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.
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.
Why does expanding from centers beat checking substrings?
A palindrome is defined by its center: once expansion stops at a mismatch, every longer span around that center is settled too. Each of the 2n - 1 centers does one monotone expansion instead of re-validating overlapping substrings from scratch — that's the n^3 to n^2 drop in one sentence.