To solve this problem, we need to count the number of distinct palindromic substrings in a given string. A palindrome is a string that reads the same forwards and backwards, and we need to consider both odd and even length palindromes.

Approach

1. Palindrome Center Expansion: Every palindrome has a center. For odd-length palindromes, the center is a single character. For even-length palindromes, the center is a pair of consecutive characters.
2. Expand Around Centers: For each center (both single and consecutive pairs), expand outwards as long as the characters on both sides are equal. Collect all unique palindromic substrings during this expansion.
3. Use a Set: To ensure we count only distinct palindromic substrings, store the substrings in a set (which automatically handles duplicates).

Solution Code

def count_distinct_palindromes(s):
    if not s:
        return 0

    palindromes = set()
    n = len(s)

    for i in range(n):
        # Expand for odd-length palindromes
        l, r = i, i
        while l >= 0 and r < n and s[l] == s[r]:
            palindromes.add(s[l:r+1])
            l -= 1
            r += 1

        # Expand for even-length palindromes
        l, r = i, i + 1
        while l >= 0 and r < n and s[l] == s[r]:
            palindromes.add(s[l:r+1])
            l -= 1
            r += 1

    return len(palindromes)

# Example usage:
# print(count_distinct_palindromes("abc"))  # Output:3
# print(count_distinct_palindromes("aaa"))  # Output:3
# print(count_distinct_palindromes("abba")) # Output:4

Explanation

1. Edge Case Handling: If the input string is empty, return 0 immediately.
2. Odd-Length Palindromes: For each character, expand outwards to check for palindromes. For example, in "racecar", the center at index 3 (character 'e') expands to form "racecar".
3. Even-Length Palindromes: For each consecutive pair of characters, expand outwards. For example, in "abba", the center at indices (1, 2) (characters 'b' and 'b') expands to form "abba".
4. Distinct Substrings: Using a set ensures that each palindromic substring is counted only once, regardless of how many times it appears in the original string.

This approach efficiently finds all distinct palindromic substrings with a time complexity of O(n²) (where n is the length of the string) and space complexity of O(n²) in the worst case (for storing all distinct palindromes). This is optimal for most practical purposes.

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