Description
Count all palindromic substring occurrences. Equal text at different positions counts separately.
Solution
def count_substrings(s):
count = 0
for center in range(len(s)):
for left,right in ((center,center),(center,center+1)):
while left >= 0 and right < len(s) and s[left] == s[right]:
count += 1
left -= 1
right += 1
return countExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
["aaa"]- Output
6
Three length-one, two length-two, and one length-three occurrences count.
Example 2
- Input
["abc"]- Output
3
Only single letters are palindromes.
Example 3
- Input
["abba"]- Output
6
Four single letters, bb, and abba contribute.
Approach
Expand from odd and even centers and count every successful expansion.
Time & space
O(n²) time; O(1) space. Here n is the input length.