1Understand
The idea
A palindrome reads the same from both ends, so compare inward with two pointers. To find palindromic substrings, expand outward from every centre: each character, and each gap between two characters for even lengths. That gives O(n²) total with O(1) extra space.
Intuition
A palindrome reads the same forward and backward, so two pointers moving inward compare characters. For substrings, expand outward from every centre, each character (odd length) and each gap between characters (even length).
That expansion is O(n²) time and O(1) extra space, which beats generating all substrings explicitly. Manacher's algorithm is O(n) but rarely required.
Whole-string palindrome checks are the inward two-pointer special case.
What you will be able to do
- Handle odd and even centres
- Normalise case and non-alphanumerics when asked
When to use it
- Longest palindromic substring
- Is it a palindrome after removing one char?
- Count palindromic substrings
2See it
Walkthrough
Expand around centers
s = "aba", odd center at index 1.
1 / 6
Try each center i. Odd: L=R=i.
Live template
Line 1 active
Complexity: time O(n²), space O(1)
Expand-around-centre is O(n²) time, O(1) space. DP dp[i][j] is also O(n²) with O(n²) space. For only checking one string, two pointers are O(n).
Read the walkthrough as text
Longest palindromic substring. s = "babad".
- Expand from index 0 (
b) →"b". From gap 0-1, no even palindrome. - From index 1 (
a): odd expand gives"bab"; record. - From index 2 (
b):"aba"also length 3. - Answer
"bab"or"aba".
In code:
- def expand(l, r): - while l >= 0 and r < n and s[l] == s[r]: - l -= 1; r += 1 - return s[l+1:r] Try all centres; keep the longest returned slice.
3Recognise it
Kinds of problems (6)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Valid palindrome (with normalisation)
Example. Palindrome after stripping non-alphanumerics.
How. Two pointers inward on filtered chars; skip or normalize case first.
Palindrome after one deletion
Example. Can become palindrome by removing one char?
How. Two pointers; on mismatch try skip left or skip right once.
Longest palindromic substring
Example. Longest substring that reads the same both ways.
How. Expand around each centre odd and even; track best span.
Count palindromic substrings
Example. Number of palindromic substrings in s.
How. Same expansion; each valid expand contributes 1 (or count centres).
Longest palindrome from letter counts
Example. Longest palindrome built from multiset of chars.
How. Use all pairs; at most one odd count char in centre.
Change one letter (break a palindrome)
Example. Lex smallest palindrome strictly smaller than s.
How. Find first position from left where s differs from reverse; decrement with carry rules.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Even centres missed
Why it happens. Expand only at index i covers odd-length centres.
How it fails. Longest even palindrome "abba" missed, only checked expand(i,i).
Fix. Also expand(i,i+1) for each i.
Brute force
Why it happens. Check every substring for correctness.
How it fails. n=500: O(n³) substring checks time out on longest palindromic substring.
Fix. Expand around centres O(n²) or Manacher.
No normalisation
Why it happens. Compare raw chars when statement already says alphanumeric only.
How it fails. "A man, a plan..." fails because spaces and case differ.
Fix. Filter to alnum lower (or problem’s rule) before two-pointer check.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.