Longest Palindromic Substring is the #10 most asked LeetCode problem globally — and one of the most important String + DP problems in interview prep.
Our analysis of 10,385 verified interview questions across 259 companies shows it appeared 89 times across 38 companies — including Google, Amazon, Meta, Microsoft, Bloomberg, Goldman Sachs, LinkedIn, DoorDash, ByteDance, and Mastercard.
There are two solid approaches: a 2D DP table (O(n²) time and space) and the cleaner expand-around-center technique (O(n²) time, O(1) space). The expand-around-center solution is shorter, easier to remember, and uses less space — making it the preferred answer in interviews.
| Metric | Value |
|---|---|
| Total Interview Appearances | 89 verified mentions |
| Companies That Ask It | 38 companies |
| Global Rank | #10 out of 10,385 questions |
| Difficulty | Medium |
| Core Patterns | Two Pointers, String, Dynamic Programming |
Google, Amazon, Meta, Microsoft, Bloomberg, Goldman Sachs, LinkedIn, DoorDash, ByteDance, Mastercard, Adobe, Agoda, Apple, Autodesk, BNY Mellon, BlackRock, Cisco, Cognizant, Dell, Deloitte, Disney, EPAM Systems, Goldman Sachs, Grab, Huawei, IBM, Infosys, J.P. Morgan, and 10 more.
LeetCode #5 — Longest Palindromic Substring
Given a string s, return the longest palindromic substring in s.
Input: s = "babad" Output: "bab" (or "aba", both valid)
Input: s = "cbbd" Output: "bb"
Input: s = "a" Output: "a"
Input: s = "racecar" Output: "racecar"Every palindrome has a center. For odd-length palindromes ("aba") the center is a single character. For even-length palindromes ("abba") the center is the gap between two identical characters.
So there are 2n - 1 possible centers in a string of length n (n single chars + n-1 gaps). For each center, expand outward as long as characters match. Track the longest expansion found.
For "abba" (n=4): centers are a, ab-gap, b, bb-gap, b, ba-gap, a → 7 = 2(4)-1 centers. The "bb" gap center expands to "abba". Always check both odd (single char) and even (gap) centers.
dp[i][j] = true if s[i..j] is a palindrome. Base cases: single chars are palindromes (dp[i][i] = true), two equal chars are palindromes. Recurrence: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Fill diagonally by increasing length.
Cleaner and preferred. For each center, expand while characters match. Update result when a longer palindrome is found.
def longestPalindrome(s: str) -> str:
start, end = 0, 0
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return l + 1, r - 1 # last valid bounds
for i in range(len(s)):
# Odd length: center at i
l1, r1 = expand(i, i)
# Even length: center between i and i+1
l2, r2 = expand(i, i + 1)
if r1 - l1 > end - start:
start, end = l1, r1
if r2 - l2 > end - start:
start, end = l2, r2
return s[start:end + 1]class Solution {
private int start = 0, maxLen = 1;
public String longestPalindrome(String s) {
for (int i = 0; i < s.length(); i++) {
expand(s, i, i); // odd length
expand(s, i, i + 1); // even length
}
return s.substring(start, start + maxLen);
}
private void expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--; r++;
}
// After loop: l+1 to r-1 is the palindrome
if (r - l - 1 > maxLen) {
maxLen = r - l - 1;
start = l + 1;
}
}
}var longestPalindrome = function(s) {
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); // odd
const [l2, r2] = expand(i, i + 1); // even
if (r1 - l1 > end - start) [start, end] = [l1, r1];
if (r2 - l2 > end - start) [start, end] = [l2, r2];
}
return s.slice(start, end + 1);
};| Approach | Time | Space |
|---|---|---|
| 2D DP Table | O(n²) | O(n²) |
| Expand Around Center | O(n²) | O(1) |
| Manacher's Algorithm | O(n) | O(n) |
Manacher's is O(n) but highly complex to implement in an interview. Expand around center is the sweet spot — simple to code, O(1) space, and clearly optimal enough to impress.
| Problem | Pattern | Key Technique |
|---|---|---|
| LC #5 Longest Palindromic Substring | Expand around center | 2n-1 centers |
| LC #647 Palindromic Substrings (count) | Expand around center | Count expansions |
| LC #125 Valid Palindrome | Two pointers | Skip non-alphanumeric |
| LC #131 Palindrome Partitioning | Backtracking + DP | Precompute palindrome table |
| LC #132 Palindrome Partitioning II | DP | Min cuts with palindrome check |
| LC #516 Longest Palindromic Subsequence | 2D DP | LCS of s and reverse(s) |
Tag all palindrome problems on DSAPrep.dev under String, Two Pointers, and Dynamic Programming.