To solve this problem, we need to count the number of distinct palindromic substrings in a given string. A palindromic substring reads the same forwards and backwards, and we need to ensure we only count each unique substring once.
Approach
The key insight is to consider two types of palindromes:
- Odd-length palindromes: These have a single character as their center.
- Even-length palindromes: These have a pair of adjacent characters as their center.
For each center, we expand outwards as long as the characters on both sides are equal. We use a set to store unique palindromic substrings, as sets automatically handle duplicates.
Solution Code
def count_distinct_palindromic_substrings(s):
n = len(s)
if n == 0:
return 0
unique_palindromes = set()
# 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]:
unique_palindromes.add(s[left:right+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]:
unique_palindromes.add(s[left:right+1])
left -= 1
right += 1
return len(unique_palindromes)
# Example usage:
# print(count_distinct_palindromic_substrings("abc")) # Output:3
# print(count_distinct_palindromic_substrings("aaa")) # Output:3
# print(count_distinct_palindromic_substrings("abba")) # Output:4
Explanation
- Odd-length palindromes: For each index
i(center), we expand left (left = i) and right (right = i). If the characters atleftandrightare equal, we add the substring to the set and continue expanding. - Even-length palindromes: For each index
i, we consider the center betweeniandi+1(soleft = iandright = i+1). We expand similarly, adding valid substrings to the set. - Unique count: The size of the set gives the number of distinct palindromic substrings.
This approach efficiently finds all unique palindromic substrings with a time complexity of O(n²) (since each center expansion takes up to O(n) steps and there are O(n) centers) and space complexity of O(k) (where k is the number of distinct palindromes). This is optimal for most practical cases.
Answer: The function count_distinct_palindromic_substrings returns the number of distinct palindromic substrings in the input string. For example, if the input is "abc", the output is 3. If the input is "aaa", the output is 3, and if the input is "abba", the output is 4. You can call this function with your input string to get the desired result.


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