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 palindrome once.

Approach

The key insight to efficiently find all palindromic substrings is to expand around centers. Each palindrome has a center:

• For odd-length palindromes, the center is a single character.
• For even-length palindromes, the center is between two consecutive characters.

We can:

1. Iterate over each possible center in the string.
2. For each center, expand outwards as long as the characters on both sides are equal, adding each valid palindrome to a set (to avoid duplicates).
3. The size of the set gives the number of distinct palindromic substrings.

Solution Code

def count_unique_palindromic_substrings(s):
    if not s:
        return 0
    unique_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]:
            unique_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]:
            unique_palindromes.add(s[left:right+1])
            left -= 1
            right += 1

    return len(unique_palindromes)

# Example usage:
print(count_unique_palindromic_substrings("aaa"))  # Output: 3

Explanation

1. Initialization: We start with an empty set to store unique palindromic substrings.
2. Odd-length Palindromes: For each character as the center, expand left and right until the characters are no longer equal. Add each valid substring to the set.
3. Even-length Palindromes: For each pair of consecutive characters as the center, expand similarly and add valid substrings to the set.
4. Result: The size of the set gives the count of distinct palindromic substrings.

This approach efficiently finds all unique palindromic substrings with a time complexity of O(n²) (since each center expansion can take up to O(n) time, and there are O(n) centers) and space complexity of O(k) (where k is the number of unique palindromic substrings). This is optimal for most practical cases.

The example input "aaa" returns 3 because the unique palindromic substrings are "a", "aa", and "aaa".

Answer: The function count_unique_palindromic_substrings returns the required count. For the input "aaa", the output is 3. So the final answer is 3.

\boxed{3}

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