Longest Palindromic Substring
Problem
Given a string s, return the longest palindromic substring in s.
- 1 ≤ s.length ≤ 1000
- s consists of ASCII characters
Example
s = "babad""bab"The brute-force approach would check every substring to see if it is a palindrome, which is O(n^3) due to substring extraction and palindrome checks. Instead, the optimal strategy expands around potential palindrome centers. For example, at index 1 ('a'), the algorithm expands left and right to check for odd-length palindromes like 'bab'. Similarly, it checks even-length palindromes by expanding around pairs of characters. The critical moment is when the algorithm finds a palindrome longer than the current longest and updates the result accordingly. This approach reduces the complexity to O(n^2) by avoiding repeated substring checks and leveraging symmetry.
Approach
Straightforward Solution
Check every substring and verify if it is a palindrome by comparing characters from both ends. This brute-force approach is O(n^3) due to O(n^2) substrings and O(n) palindrome checks, which is inefficient for large inputs.
Core Observation
A palindrome reads the same forwards and backwards. Any palindrome can be expanded from its center. Since palindromes can be odd or even length, centers can be single characters or pairs of characters.
Path to Optimal
PreviewThe key recognition signals are 'longest palindromic substring' and 'substring' (contiguous), which suggest expanding around centers…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewIterate through each index in the string, expanding around it to find the longest odd-length palindrome, then expand around the gap between this index and the next to find the longest even-length palindrome. Track the longest palindrome found and update the result accordingly…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n^2)
For each of the n indices, the algorithm expands outward at most n times in the worst case, resulting in O(n^2) total operations.
Space
O(1)
Only a few variables are used to track indices and the current longest palindrome; no additional data structures proportional to input size are needed.
Pattern Spotlight
Two Pointers (Expand Around Center)
To find palindromes efficiently, treat each character and each gap between characters as a center and expand pointers outward symmetrically until the palindrome property breaks, thereby avoiding redundant substring checks.
Solution
| 1 | class Solution:
|
| 2 | def longestPalindrome(self, s: str) -> str:
|
| 3 | res = ""
|
| 4 | res_len = 0
|
| 5 |
|
| 6 | for i in range(len(s)):
|
| 7 | l, r = i, i
|
| 8 | while l >= 0 and r < len(s) and s[l] == s[r]:
|
| 9 | if (r - l + 1) > res_len:
|
| 10 | res = s[l:r+1]
|
| 11 | res_len = r - l + 1
|
| 12 | l -= 1
|
| 13 | r += 1
|
| 14 |
|
| 15 | l, r = i, i + 1
|
| 16 | while l >= 0 and r < len(s) and s[l] == s[r]:
|
| 17 | if (r - l + 1) > res_len:
|
| 18 | res = s[l:r+1]
|
| 19 | res_len = r - l + 1
|
| 20 | l -= 1
|
| 21 | r += 1
|
| 22 |
|
| 23 | return res |
Step-by-Step Solution
Initialize Result Variables to Track Longest Palindrome
| 3 | res = ""
|
| 4 | res_len = 0
|
Objective
To prepare variables that store the longest palindrome substring found and its length.
Key Insight
Tracking the longest palindrome and its length allows the algorithm to update the result only when a longer palindrome is found during expansions. Initializing with empty string and zero length ensures correctness even for single-character inputs.
Interview Quick-Check
Core Logic
The variables `res` and `res_len` maintain the current longest palindrome substring and its length, enabling efficient updates.
State & Boundaries
Starting with an empty string and zero length handles edge cases where the input string length is 1.
Expand Around Single Character Centers to Find Odd-Length Palindromes
To find the longest odd-length palindrome centered at each index by expanding pointers outward symmetrically.
Expand Around Adjacent Character Pairs to Find Even-Length Palindromes
To find the longest even-length palindrome centered between each pair of adjacent characters by expanding pointers outward symmetrically.
Return the Longest Palindromic Substring Found
To output the longest palindrome substring after all expansions have been checked.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
while l >= 0 and r < len(s) and s[l] == s[r]:Expand pointers outward while within bounds and characters at pointers match.
Expanding outward symmetrically from the center is the core mechanism that efficiently finds palindromes without checking all substrings.
while l >= 0 and r < len(s) and s[l] == s[r]:Expand pointers outward while within bounds and characters at pointers match for even-length palindrome.
This expansion is critical to capture even-length palindromes, which would be missed if only single centers were considered.
Full line-by-line criticality + rationale for all 18 lines available on Pro.
Test Your Understanding
Why does expanding around centers guarantee finding all palindromic substrings without missing any?
See the answer with Pro.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct Longest Palindromic Substring from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Longest Palindromic Substring drill