如何修改代码计算字符串中唯一回文子串的数量？

你现有的代码只能统计所有回文子串的总数，没法去重。要统计唯一回文子串的数量，核心思路是用一个集合存储找到的每个回文子串——集合会自动忽略重复元素，最后集合的大小就是你要的结果。

先给你修正并修改后的完整代码：

#include <unordered_set>
#include <string>

template <class T>
int uniqueSubPalindrome(T s)
{
    std::unordered_set<std::string> uniquePalindromes;
    int n = s.length();

    // 处理奇数长度的回文子串（中心为单个字符）
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; (i + j) < n && (i - j) >= 0; j++)
        {
            if (s[i + j] != s[i - j])
            {
                break;
            }
            // 提取当前回文子串并加入集合
            std::string sub = s.substr(i - j, 2 * j + 1);
            uniquePalindromes.insert(sub);
        }
    }

    // 处理偶数长度的回文子串（中心为两个字符之间）
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; (i + j + 1) < n && (i - j) >= 0; j++)
        {
            if (s[i + j + 1] != s[i - j])
            {
                break;
            }
            // 提取当前回文子串并加入集合
            std::string sub = s.substr(i - j, 2 * j + 2);
            uniquePalindromes.insert(sub);
        }
    }

    // 返回集合的大小，即唯一回文子串的数量
    return uniquePalindromes.size();
}

修改说明 #

• 把原来的计数变量res换成std::unordered_set<std::string>，用它存储所有找到的回文子串，自动实现去重
• 每次确认是回文子串时，用substr提取对应子串：
  • 奇数长度子串：起始位置i-j，长度2*j+1
  • 偶数长度子串：起始位置i-j，长度2*j+2
• 修正了原代码的参数错误：原函数参数是s，但代码里误用了未定义的str，现在统一为s
• 最后返回集合的size()，就是唯一回文子串的总数

如果担心unordered_set的性能，也可以换成std::set，不过前者的插入和查找平均时间复杂度更低。

内容的提问来源于stack exchange，提问作者Mudassir Waheed