Longest Palindromic Substring
Asked at Google, Meta, Amazon, Apple, Microsoft, Oracle, Adobe, Salesforce, Walmart
Problem
Given a string, find the longest substring that is a palindrome. This problem tests your understanding of expand-around-center or dynamic programming approaches and is a staple of FAANG interviews.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Apple | Medium | View all Apple questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Oracle | Medium | View all Oracle questions → |
| Adobe | Medium | View all Adobe questions → |
| Salesforce | Medium | View all Salesforce questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Brute force: check every substring. There are n*(n+1)/2 substrings. For each, check if it's a palindrome in O(n). Total: O(n³). Too slow.
Better: dynamic programming. dp[i][j] = true if s[i:j+1] is a palindrome. Build from shorter to longer. O(n²) time and space. Works but space-heavy.
Best: expand around center. A palindrome mirrors around its center. For each possible center, expand outward while characters match. Track the longest one found.
Why expand-around-center works: every palindrome has a center. Odd-length palindromes have a single character center (e.g., "aba" centered at 'b'). Even-length have a gap center (e.g., "abba" centered between the two 'b's). So there are 2n-1 possible centers.
Visual walkthrough for "babad":
b a b a d
0 1 2 3 4
- Center 0 (b): expand → "b", length 1
- Center 1 (a): expand → "a", then "bab" (b==b), then stop. Max = "bab", length 3
- Center 2 (b): expand → "b", then "aba" (a==a), then stop. Max = "aba", length 3
- Center 3 (a): expand → "a", then "d" (d!=b). Max still 3 - Center 4 (d): expand → "d", length 1
- Even centers: "ba" (b!=a), "ab" (a!=b), "ba" (b!=a), "ad" (a!=d). None longer.
Result: "bab" or "aba" (both valid)
Edge cases: single character (return it), all same characters (return entire string), no palindrome longer than 1 (return first char).
Optimal Approach
For each index i in the string:
Odd-length palindrome: expand from center i. Set left = i, right = i. While left >= 0 and right < n and
s[left]==s[right], expand outward (left--, right++). Record the palindrome.Even-length palindrome: expand from center between i and i+1. Set left = i, right = i+1. Same expansion logic.
After checking both centers at each position, update the longest palindrome found.
The expand function returns the palindrome string. We compare lengths and keep the longest.
Time: O(n²) — n centers, each expansion takes O(n) worst case. Space: O(1) — just pointers, no extra data structures.
What Trips People Up in Real Interviews
Confusing "substring" with "subsequence." A substring is contiguous. "babad" has "bab" as a substring palindrome, but "aceca" is not a substring of "abcba" — it's a subsequence.
Trying to use dynamic programming on the full string without realizing that expand-from-center is simpler and O(1) space. For each position, try expanding outward from (i, i) and (i, i+1).
Forgetting to handle both odd-length and even-length palindromes. "aba" is odd-length (center is b), "abba" is even-length (center is between the two b's). You need both.
Not updating the result correctly. Keep track of the start index and max length, not just the length. When you find a longer palindrome, update both.
Returning s[l:r] from the expand function instead of s[l+1:r]. After the while loop exits, l and r have each moved one step past the valid palindrome boundary.
Solution Code
def longestPalindrome(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return s[l+1:r]
best = ""
for i in range(len(s)):
odd = expand(i, i)
even = expand(i, i + 1)
best = max(best, odd, even, key=len)
return bestFrequently Asked Questions
What is the Longest Palindromic Substring problem?
Given a string, find the longest substring that is a palindrome. This problem tests your understanding of expand-around-center or dynamic programming approaches and is a staple of FAANG interviews.
How do you solve Longest Palindromic Substring?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Longest Palindromic Substring?
Longest Palindromic Substring is asked at Google, Meta, Amazon, Apple, Microsoft, Oracle, Adobe, Salesforce, Walmart. It is a medium difficulty problem.
What are common mistakes on Longest Palindromic Substring?
- Confusing "substring" with "subsequence." A substring is contiguous. "babad" has "bab" as a substring palindrome, but "aceca" is not a substring of "abcba" — it's a subsequence.
- Trying to use dynamic programming on the full string without realizing that expand-from-center is simpler and `O(1)` space. For each position, try expanding outward from (i, i) and (i, i+1).
- Forgetting to handle both odd-length and even-length palindromes. "aba" is odd-length (center is b), "abba" is even-length (center is between the two b's). You need both.
- Not updating the result correctly. Keep track of the start index and max length, not just the length. When you find a longer palindrome, update both.
- Returning `s[l:r]` from the expand function instead of `s[l+1:r]`. After the while loop exits, l and r have each moved one step past the valid palindrome boundary.