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 each possible 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 the same. We use a set to track unique palindromic substrings since sets automatically handle duplicates.

Solution Code

def count_distinct_palindromes(s):
    palindromes = set()
    n = len(s)

    for i in range(n):
        # Expand around odd-length palindromes (center at i)
        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 around even-length palindromes (center between i and i+1)
        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)

# Read input and output the result
s = input().strip()
print(count_distinct_palindromes(s))

Explanation

1. Initialization: We start with an empty set palindromes to store unique palindromic substrings.
2. Odd-length Palindromes: For each index i, we expand left (l) and right (r) from i until the characters at l and r are not equal. Each valid substring s[l:r+1] is added to the set.
3. Even-length Palindromes: For each index i, we expand left from i and right from i+1 until the characters at l and r are not equal. Each valid substring is added to the set.
4. Result: The size of the set gives the count of distinct palindromic substrings.

This approach efficiently finds all palindromic substrings with a time complexity of O(n²) (since each expansion can take up to O(n) time and there are O(n) centers), which is optimal for most practical purposes. The space complexity is O(n²) in the worst case (when all substrings are palindromic), but using a set ensures we only store unique values.

Example:

• Input: "aaa" → Output: 3 (distinct palindromes: "a", "aa", "aaa").
• Input: "abba" → Output:4 (distinct palindromes: "a", "b", "bb", "abba").

This solution handles all edge cases, including empty strings (returns 0) and single-character strings (returns 1). It correctly counts all unique palindromic substrings in the input string.

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