Lesson 3.4 · Strings
Palindromes: Check and Expand
Two pointers check a palindrome from the outside in; expanding from a centre finds palindromes from the inside out.
12 min
Think of it like this
A palindrome reads the same forwards and backwards, like "racecar". Checking one is like two people reading a word from opposite ends and stopping at the first disagreement. Finding one is like standing in the middle and stepping outwards on both sides while the letters still match.
1.Outside in: checking
Put left at the start and right at the end. While left < right, compare the characters; if they differ it isn't a palindrome; otherwise step both inwards. O(n) time, O(1) space.
2.Inside out: expanding around a centre
Every palindrome has a centre: a single character (odd length, "aba") or the gap between two characters (even length, "abba"). From each of the 2n − 1 possible centres, expand while both sides match. The longest expansion is the longest palindromic substring, in O(n²) time and O(1) space.
s = "racecar", centre at index 3Step 1/4Start with L = R = 3 (odd-length centre 'e').
Remember
- Check palindromes with two pointers from the ends.
- Find them by expanding from each of the 2n − 1 centres.
- Remember even-length centres between characters.
Common mistakes
- Only trying single-character centres, which misses even palindromes like "abba".
- Off-by-one when converting the final L and R back to a substring.