DSA Tracker

Visualize

Palindromic Substrings

Expand around every center, counting each successful expansion

time O(n^2)space O(1)

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.

Details

Animated on: s = "aabaa" — count how many substrings of s are palindromes (same substring at different positions counts separately).

Problem:Palindromic SubstringsMedium

Expand around every center, counting each successful expansion

step 1 / 11

a
[0]
a
[1]
b
[2]
a
[3]
a
[4]

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.

Pseudocode
1FUNCTION countPalindromes(S):
2  count <- 0
3  FOR center <- 0 TO 2 * LENGTH(S) - 2
4    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 + 1
8      l <- l - 1
9      r <- r + 1
10  RETURN count

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. 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.
  2. Center on character 0 ('a'): pushing outward stayed symmetric 1 time, so this center alone contributes 1 palindrome — the widest is "a" over indices 0..0. Expansion stopped because the left side ran off the start of the string. Total is now 1.
  3. Center on the gap between 0 ('a') and 1 ('a'): pushing outward stayed symmetric 1 time, so this center alone contributes 1 palindrome — the widest is "aa" over indices 0..1. Expansion stopped because the left side ran off the start of the string. Total is now 2.
  4. Center on character 1 ('a'): pushing outward stayed symmetric 1 time, so this center alone contributes 1 palindrome — the widest is "a" over indices 1..1. Expansion stopped because S[0]='a' != S[2]='b'. Total is now 3.
  5. Center on the gap between 1 ('a') and 2 ('b'): the very first comparison fails ('a' != 'b'), so no even-length palindrome can sit here. Total stays 3.
  6. Center on character 2 ('b'): pushing outward stayed symmetric 3 times, so this center alone contributes 3 palindromes — the widest is "aabaa" over indices 0..4. Expansion stopped because the left side ran off the start of the string. Total is now 6.
  7. Center on the gap between 2 ('b') and 3 ('a'): the very first comparison fails ('b' != 'a'), so no even-length palindrome can sit here. Total stays 6.
  8. Center on character 3 ('a'): pushing outward stayed symmetric 1 time, so this center alone contributes 1 palindrome — the widest is "a" over indices 3..3. Expansion stopped because S[2]='b' != S[4]='a'. Total is now 7.
  9. Center on the gap between 3 ('a') and 4 ('a'): pushing outward stayed symmetric 1 time, so this center alone contributes 1 palindrome — the widest is "aa" over indices 3..4. Expansion stopped because the right side ran off the end of the string. Total is now 8.
  10. Center on character 4 ('a'): pushing outward stayed symmetric 1 time, so this center alone contributes 1 palindrome — the widest is "a" over indices 4..4. Expansion stopped because the right side ran off the end of the string. Total is now 9.
  11. All 9 centers have been expanded. Each successful expansion was one distinct palindromic substring, so "aabaa" contains 9 of them.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Palindromic Substrings in the editorAll Strings problemsBack to roadmap