Pattern visualizer
Palindromic Substrings
Checking every substring separately re-reads the same characters over and over. Instead, notice that a palindrome is symmetric around a middle, and that middle is either a single character (odd length) or the gap between two characters (even length). Sit on each of those centers and push the two sides outward: as long as the characters match you have found one more palindrome, and the moment they differ every wider span around that center is ruled out too. Counting one for each successful expansion counts every palindromic substring exactly once, because each palindrome has exactly one center. Animated on: s = "aabaa" — count how many substrings of s are palindromes (same substring at different positions counts separately)..
Expand around every center, counting each successful expansion
s="aabaa". Every palindrome has a middle, so instead of testing all substrings we sit on each of the 9 possible centers (5 single characters and 4 gaps between characters) and push outward while the two sides still match.
1FUNCTION countPalindromes(S):2 count <- 03 FOR center <- 0 TO 2 * LENGTH(S) - 24 l <- FLOOR(center / 2)5 r <- l + (center MOD 2)6 WHILE l >= 0 AND r <= LENGTH(S) - 1 AND S[l] = S[r]7 count <- count + 18 l <- l - 19 r <- r + 110 RETURN count
← / → step · space play · Home restart