Given a string, return the number of palindromic substrings in it.
MediumGiven a string s, return the number of its substrings that are palindromes. A palindrome reads the same forward and backward. Substrings at different positions count separately, even if they contain the same characters.
Example 1
Input: s = "abc" Output: 3
The palindromes are a, b and c.
Example 2
Input: s = "aaa" Output: 6
a appears three times, aa twice and aaa once.
Constraints
1 <= s.length <= 1000scontains only lowercase English letters.
Approach
Checking every substring for being a palindrome takes O(n³) time. Flip it around: every palindrome has a center, either a single character for odd lengths or the gap between two characters for even lengths. Start from each of the 2n - 1 centers and move two pointers outward one step at a time while the characters on both sides match. Each successful step is a palindrome to count. As soon as the characters differ, no longer palindrome can share that center, so move on to the next one.
The Longest Palindromic Substring lesson uses the same expansion to find the longest palindrome instead of counting them all.
Steps
- Loop over all
2n - 1centers. For centeri, startleftati // 2andrightatleft + i % 2. - While both pointers are in range and
s[left] == s[right], add one to the count, then moveleftback andrightforward. - Return the count.
Complexity
- Time:
O(n²). Each center can expand up ton / 2steps. - Space:
O(1).
Common mistakes
- Expanding only from single characters. That misses every even-length palindrome, such as
aa. - Removing duplicates with a set. Substrings at different positions count separately, so
"aaa"has threeas.


