ai

SUNNYDREAM · 2025-07-20 18:46:29 · 题解

题解：统计至少包含k个不同字符的子串数量

题目分析

我们需要统计给定字符串中所有满足包含至少k个不同字符的子串数量。子串是指字符串中连续的字符序列。

方法思路

这个问题可以使用滑动窗口（双指针）技术高效解决。具体步骤如下：

1. 初始化：使用两个指针left和right表示窗口的左右边界，初始都指向字符串开始位置。
2. 滑动窗口：
   • 向右移动right指针，扩展窗口，直到窗口内包含至少k个不同字符。
   • 一旦满足条件，所有以right结尾的子串（从left到right，left+1到right，...）都满足条件，可以直接计算数量。
   • 然后尝试移动left指针缩小窗口，检查是否仍然满足条件。
3. 哈希表记录：使用哈希表记录窗口内各字符的出现次数，以快速判断不同字符的数量。

这种方法的时间复杂度是O(n)，因为我们每个字符最多被访问两次（被left和right指针各一次）。

解决代码

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

long long countSubstrings(const string &s, int k) {
    int n = s.size();
    long long res = 0;
    for (int unique = 1; unique <= 26; ++unique) {
        int left = 0, right = 0;
        unordered_map<char, int> freq;
        int count = 0;
        long long temp = 0;
        while (right < n) {
            if (freq[s[right]] == 0) count++;
            freq[s[right]]++;
            while (count > unique) {
                freq[s[left]]--;
                if (freq[s[left]] == 0) count--;
                left++;
            }
            temp += right - left + 1;
            right++;
        }
        left = 0, right = 0;
        freq.clear();
        count = 0;
        while (right < n) {
            if (freq[s[right]] == 0) count++;
            freq[s[right]]++;
            while (count > unique - 1) {
                freq[s[left]]--;
                if (freq[s[left]] == 0) count--;
                left++;
            }
            temp -= right - left + 1;
            right++;
        }
        if (unique >= k) res += temp;
    }
    return res;
}

int main() {
    string S;
    int k;
    cin >> S >> k;
    cout << countSubstrings(S, k) << endl;
    return 0;
}

代码解释

1. countSubstrings函数：计算满足条件的子串数量。
   • 外层循环枚举可能的唯一字符数量（1到26）。
   • 内层使用滑动窗口计算恰好包含unique个不同字符的子串数量。
   • 通过两次滑动窗口的差值计算恰好包含unique个字符的子串数量。
   • 累加所有unique ≥ k的情况得到最终结果。
2. 主函数：读取输入并调用countSubstrings函数输出结果。

这种方法高效且易于理解，适用于大规模数据输入。