Reading the same both ways
A palindrome reads identically forward and backward, such as the word level. Finding palindromic substrings is a common task, and the most intuitive method is expand around centre.
The centre idea
Every palindrome has a centre. The trick is that there are two kinds:
- Odd length palindromes have a single character centre, like the middle of r a c e c a r.
- Even length palindromes have a centre between two characters, like the gap in the middle of a b b a.
For each possible centre you expand two pointers outward, one left and one right, as long as the characters they point to are equal. The moment they differ, or a pointer runs off the end, the longest palindrome at that centre is fixed.
Cost and reach
There are about twice as many centres as characters, and each expansion can stretch across much of the string, so the worst case work is proportional to length squared. It is simple, needs no extra structures, and naturally records the longest palindrome found across all centres.
Key idea
Expand around centre tries every odd and even centre and grows two pointers outward while characters match; it is simple and structure free but its worst case work grows with the square of the length.