5. Longest Palindromic Substring
Asked at Google, Meta, Amazon, Apple and 8 more
Difficulty
Medium
Time
O(n^2)
Space
O(1)
Pattern
String
Companies
12
Problem
You are given a string s. Return the longest substring of s that reads the same forwards and backwards (a palindrome).
A substring must be a contiguous block of characters — you cannot skip characters. If several substrings tie for the longest length, any one of them is accepted as the answer.
A single character is always a palindrome, so the answer always has length at least 1.
Find the longest mirrored block
Constraints
- ●
1 <= s.length <= 1000 - ●
s consists of only digits and English letters
Examples
s = "babad"babs = "cbbd"bbAsked At
12 companies| 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 → |
| Bloomberg | Medium | View all Bloomberg questions → |
| Goldman Sachs | Medium | View all Goldman Sachs questions → |
| Visa | Medium | View all Visa 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.
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.
Expand around every center
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
O(n^2) timedef 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 runs in O(n^2) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Longest Palindromic Substring?
Longest Palindromic Substring is asked at Google, Meta, Amazon, Apple, Microsoft, Oracle, Adobe, Salesforce, Walmart, Bloomberg, Goldman Sachs, Visa. 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.