1. One-Liner
Find the longest contiguous palindrome in S — often solved in O(n²) by expanding around centers or O(n) with Manacher.
2. The Problem It Solves
Used in symmetry detection, DNA inverted repeats, and as a stepping stone to palindrome partitioning / minimum cuts problems.
3. The Core Idea
Every palindrome has a center (one character for odd length, between two for even). Expand while boundary characters match; track the maximum radius or length.
4. How It Works (Table)
| Step | What Happens |
|---|---|
| 1 | For each center c from 0 to n-1 (odd) and each gap (even). |
| 2 | While L ≥ 0, R < n, and S[L]==S[R], decrement L, increment R. |
| 3 | Record best R-L-1 length and substring bounds. |
| 4 | Alternative: DP dp[i][j] = palindrome iff S[i]==S[j] and (j-i<2 or dp[i+1][j-1]). |
5. Dry Run Example
"babad" — longest length 3 ("bab" or "aba"). Expand around 'a' at index 2 for odd case.
6. Key Properties
| Property | Value |
|---|---|
| Expand centers | O(n²) time, O(1) space |
| Manacher | O(n) time for same problem |
7. Where It Is Used
| Domain | Use |
|---|---|
| Interviews | Classic medium string task |
| Bio | Palindromic repeats |
| UI | Fun palindrome highlights |
8. Interview Tips
Mention two center types (odd/even). Upgrade to Manacher if interviewer pushes linear time.
9. Comparison with Other Algorithms
| Approach | Time |
|---|---|
| Brute | O(n³) |
| Center expand | O(n²) |
| Manacher | O(n) |
10. Complexity
| Metric | Value |
|---|---|
| Center expansion | O(n²) time, O(1) extra |
| DP table | O(n²) time and space |
Implementation Example (PYTHON)
def longest_palindrome_center(s):
if not s:
return ''
start, maxlen = 0, 1
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return r - l - 1
for i in range(len(s)):
odd = expand(i, i)
even = expand(i, i + 1)
cur = max(odd, even)
if cur > maxlen:
maxlen = cur
start = i - (cur - 1) // 2
return s[start : start + maxlen]