To solve this problem, we need to count the number of non-empty palindromic substrings in a given string. A palindromic substring reads the same forwards and backwards.
Approach
The key insight to efficiently count palindromic substrings is to use the expand around centers technique. This approach leverages the fact that every palindrome has a center:
- Odd-length palindromes: The center is a single character.
- Even-length palindromes: The center is between two characters.
For each center, we expand outwards as long as the characters on both sides are equal, counting valid palindromic substrings as we go. This method ensures we cover all possible palindromic substrings with a time complexity of O(n²), which is efficient for typical input sizes.
Solution Code
def count_palindromic_substrings(s):
n = len(s)
count = 0
# Check for odd-length palindromes
for i in range(n):
left, right = i, i
while left >= 0 and right < n and s[left] == s[right]:
count += 1
left -= 1
right += 1
# Check for even-length palindromes
for i in range(n - 1):
left, right = i, i + 1
while left >= 0 and right < n and s[left] == s[right]:
count += 1
left -= 1
right += 1
return count
# Read input and output the result
s = input().strip()
print(count_palindromic_substrings(s))
Explanation
- Odd-length palindromes: For each character in the string, we start with the character as the center and expand outwards. For each valid expansion (both sides are equal), we increment the count.
- Even-length palindromes: For each pair of consecutive characters, we start with the pair as the center and expand outwards, counting valid palindromes.
This approach efficiently covers all possible palindromic substrings, ensuring we do not miss any. The overall time complexity is O(n²) because each center expansion can take up to O(n) steps, and there are O(n) centers (n for odd, n-1 for even).
Example Walkthrough
Let's take the string "aaa" to see how the code works:
- Odd-length:
- Center at index 0: count +=1 (substring "a").
- Center at index1: count +=1 ("a"), then expand to index0 and 2 → count +=1 ("aaa").
- Center at index2: count +=1 ("a").
- Total for odd: 4.
- Even-length:
- Center between index0 and 1: count +=1 ("aa").
- Center between index1 and2: count +=1 ("aa").
- Total for even:2.
- Total:4+2=6, which is correct.
This method works for all cases and is optimal for the problem constraints.


作者声明:本文包含人工智能生成内容。