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 find all palindromic substrings is to expand around each center of the string. Palindromes can be of two types:

1. Odd-length: These have a single character as their center (e.g., "aba" with center at 'b').
2. 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. We collect all unique palindromic substrings using a set to avoid duplicates. Finally, the size of the set gives the number of distinct palindromic substrings.

Solution Code

s = input().strip()
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]:
        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]:
        palindromes.add(s[left:right+1])
        left -= 1
        right += 1

print(len(palindromes))

Explanation

1. Odd-length Palindromes: For each index i, we start with left = i and right = i (center at i). We expand left and right as long as the characters are equal, adding the substring s[left:right+1] to the set.
2. Even-length Palindromes: For each index i, we start with left = i and right = i+1 (center between i and i+1). We expand similarly, adding valid even-length palindromes to the set.
3. Distinct Count: The set automatically handles duplicates, so the size of the set is the number of distinct palindromic substrings.

Example Walkthrough

Let’s take the string "abba":

• Odd-length: Centers at 0 ('a'), 1 ('b'), 2 ('b'), 3 ('a') → adds "a", "b", "b", "a".
• Even-length: Center between 1 and 2 ('b' and 'b') → expands to "bb" then to "abba" → adds "bb", "abba".
• Set: {"a", "b", "bb", "abba"} → size is 4 (correct).

This approach efficiently finds all distinct palindromic substrings with a time complexity of O(n²) (worst case) and space complexity of O(n²) (for storing unique substrings). This is feasible for most practical constraints (e.g., n ≤ 1000).

Answer: The code returns the number of distinct palindromic substrings. For the input string, the output is the size of the set of unique palindromes. For example, input "aaa" → output is 3. Input "abba" → output is4. Input "abc" → output is 3. etc. So the final answer is the code as provided.

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