Dropping a stone in a pond and watching the ripple spread equally in both directions until the banks stop matching.
Clues that point here
→ Longest palindromic substring
→ Count palindromic substrings
→ Symmetry around a middle point
→ n up to a few thousand (O(n²) is fine)
Not this pattern when
✕ n is very large and O(n) is required (Manacher's algorithm)
✕ You need palindromic subsequences, not substrings (DP)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Expand Around Center · template
int expand(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1; // length of the palindrome found
}
// for each i: try expand(s, i, i) (odd length) and expand(s, i, i + 1) (even length)