String matching, hashing, and palindrome · HTML
Odd centers are (i,i), even centers (i,i+1); expand while s[l]==s[r].
Recognition signals
- The target is a contiguous palindrome
- Longest palindrome or palindrome count is needed
- Quadratic time is acceptable with constant extra space
- Both odd and even lengths matter
- Symmetry around a center is the defining structure
False friends
| Signal | Why it is different |
|---|
| Palindromic subsequence | A subsequence may skip characters, so center expansion misses answers; use DP. |
| Many interval-palindrome queries | Repeated expansion is costly; consider DP, hashing, or precomputed Manacher radii. |
Core invariant
At loop entry s[l+1:r] is palindromic; equal new endpoints preserve symmetry.
State, transition, and processing order
| Item | Definition |
|---|
| State | Current endpoints, best interval, and optionally a palindrome counter. |
| Transition | Expand from every odd and even center; on success update the answer, then decrement l and increment r. |
| Frontier / order | The two endpoints are a symmetric frontier; the first mismatch rules out every larger radius at that center. |
Python skeleton
def palindromes_by_center(s):
best = (0, 0)
count = 0
def grow(l, r):
nonlocal best, count
while l >= 0 and r < len(s) and s[l] == s[r]:
count += 1
if r-l > best[1]-best[0]: best = (l, r)
l -= 1; r += 1
for i in range(len(s)):
grow(i, i)
grow(i, i+1)
l, r = best
return s[l:r+1], count
Correctness sketch
- Every palindrome has one center and radius.
- The algorithm enumerates all 2n-1 odd/even centers.
- For one center it checks radii in order, and a mismatch forbids larger radii.
- Thus each palindrome is counted once and a longest one is recorded.
Complexity
| Time | Space | Parameters |
|---|
| O(n²) worst case | O(1) excluding output | string length n; Manacher reduces the bound to O(n) |
Edge cases
- Handle the empty string separately
- A single character is a palindrome
- Even centers lie between characters
- Tie-breaking among longest answers must be specified
- All-equal input realizes quadratic time
Error patterns
| Pattern | Why it fails / fix |
|---|
| Only odd centers | Every even-length palindrome is missed. |
| Bounds checked after indexing | Validate endpoints before reading characters. |
| Confusing radius and length | Odd and even formulas differ; storing endpoints avoids ambiguity. |
Selection and exclusion rules
- Quadratic time is acceptable and clarity matters: center expansion.
- Large contiguous-palindrome workloads: Manacher.
- Palindromic subsequence: interval DP.
- Many dynamic palindrome checks: hashing or a specialized structure.
Original micro-example
| Part | Detail |
|---|
| Result | The longest palindrome is aba, and there are five palindromic substrings. |
| Scenario | String abac. |
| Walkthrough | Center b grows to aba; four single characters contribute four more, while other expansions stop immediately. |
Recall prompts
My notes