Given a string s, return the number of palindromic substrings it contains — every occurrence counts separately, even if the text of two substrings is identical.
Example
Input s = "aaa"
Output 6
Key Pointers
Same center-expansion idea as Longest Palindromic Substring, but every successful expansion step is itself a palindrome worth counting, not just the longest one.
Each expansion step (while the characters still match) represents one more palindromic substring centered there — the count can be accumulated during expansion, not checked afterward.
2n − 1 centers total (n odd, n−1 even) keeps this O(n²) overall.
Step-by-Step Analysis
Initialize a counter to 0.
Write a helper that expands from (left, right) while the characters match, incrementing the counter once per successful match before moving further out.
For each index i, call the helper for the odd center (i, i) and the even center (i, i+1).
Return the total count after checking every center.
Complexity
Time: O(n²) — Space: O(1)
Code
def countSubstrings(s: str) -> int:
count = 0
def expand(left: int, right: int) -> None:
nonlocal count
while left >= 0 and right < len(s) and s[left] == s[right]:
count += 1
left -= 1
right += 1
for i in range(len(s)):
expand(i, i)
expand(i, i + 1)
return count
Code Explanation
How the solution above works, piece by piece.
Same centre-expansion idea as Longest Palindromic Substring, but count every palindrome instead of keeping the longest.
Each index is an odd centre (i, i) and, with its right neighbour, an even centre (i, i + 1).
Every successful step of the expansion is one more palindromic substring, so count += 1 inside the loop.
Expansion stops at the first mismatch: anything wider around that centre can't be a palindrome either.
O(n²) time, O(1) space.
Visual Walkthrough
Running it on s = "aaa":
Each row is one palindrome counted by the loop: three single letters, two "aa" and one "aaa" = 6.