专栏文章

ai

SSUNNYDREAM
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miotn49s
此快照首次捕获于
2025/12/03 00:57
3 个月前
此快照最后确认于
2025/12/03 00:57
3 个月前
查看原文

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

题目分析

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

方法思路

这个问题可以使用滑动窗口（双指针）技术高效解决。具体步骤如下：
  1. 初始化：使用两个指针left和right表示窗口的左右边界，初始都指向字符串开始位置。
  2. 滑动窗口：
    • 向右移动right指针，扩展窗口，直到窗口内包含至少k个不同字符。
    • 一旦满足条件，所有以right结尾的子串（从left到right，left+1到right，...）都满足条件，可以直接计算数量。
    • 然后尝试移动left指针缩小窗口，检查是否仍然满足条件。
  3. 哈希表记录：使用哈希表记录窗口内各字符的出现次数，以快速判断不同字符的数量。
这种方法的时间复杂度是O(n)，因为我们每个字符最多被访问两次（被left和right指针各一次）。

解决代码

CPP
#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函数输出结果。
这种方法高效且易于理解，适用于大规模数据输入。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...