To solve this problem, we need to find the number of distinct palindromic substrings in a given string. A palindromic substring reads the same forwards and backwards, and we need to count each unique substring only once.
Approach
The key insight to efficiently find all palindromic substrings is to expand around each center of potential palindromes. Palindromes can be of two types:
- Odd-length: These have a single character as their center (e.g., "aba" with center at 'b').
- Even-length: These have two consecutive characters as their center (e.g., "abba" with center between the two 'b's).
For each center, we expand outwards as long as the characters on both sides are equal, adding each valid palindromic substring to a set (to ensure uniqueness). The size of this set gives the number of distinct palindromic substrings.
Solution Code
s = input().strip()
distinct_palindromes = set()
n = len(s)
for i in range(n):
# Expand for odd-length palindromes
left, right = i, i
while left >= 0 and right < n and s[left] == s[right]:
distinct_palindromes.add(s[left:right+1])
left -= 1
right += 1
# Expand for even-length palindromes
left, right = i, i + 1
while left >= 0 and right < n and s[left] == s[right]:
distinct_palindromes.add(s[left:right+1])
left -= 1
right += 1
print(len(distinct_palindromes))
Explanation
- Initialization: We start with an empty set to store distinct palindromic substrings.
- Odd-length Palindromes: For each character in the string, we treat it as the center and expand outwards. We add each valid palindrome to the set.
- Even-length Palindromes: For each pair of consecutive characters, we treat them as the center and expand outwards, adding valid palindromes to the set.
- Result: The size of the set (number of unique palindromic substrings) is printed as the result.
Key Notes
- Uniqueness: Using a set ensures that each palindromic substring is counted only once, even if it appears multiple times in the original string.
- Efficiency: The time complexity is O(n²) (since each of the n characters can expand up to n times), which is feasible for most practical input sizes. The space complexity is O(n²) in the worst case (if all substrings are distinct palindromes).
This approach efficiently finds all distinct palindromic substrings and handles all edge cases (empty string, single character, etc.) correctly.


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