BestCoder Round #81 (Div.2) 1004 String：雙指針統計含 K 種字符的子串數

題目大意

給定一個僅包含小寫字母的字符串 S 及整數 K，求有多少個非空子串恰好包含 K 種不同的字符。字符串長度可達 10^6，需 O(N) 或 O(N log N) 算法。

解題思路：滑動窗口 + 雙指針

固定左端點 i，找到最小的右端點 j 使得 S[i..j] 包含至少 K 種字符。此時以 i 為起點、長度 ≥ j-i+1 的所有子串均合法，共 n - j 個。將所有 i 的貢獻累加即為答案。

關鍵細節

• 維護一個大小 26 的計數陣列 cnt[26] 記錄窗口內各字符出現次數。
• get_cnt() 返回當前窗口不同字符種類數。
• 右指針 j 只單調右移，左指針 i 遍歷時收縮窗口，總複雜度 O(N)。
• 答案可能很大，需用 long long 並對 1e9+7 取模（題目要求）。

參考代碼 (C++)

#include <iostream>
#include <cstring>
using namespace std;

const int MOD = 1000000007;
const int MAXN = 1000009;
char str[MAXN];
int cnt[26];

inline int distinct() {
    int c = 0;
    for (int i = 0; i < 26; ++i) if (cnt[i]) ++c;
    return c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        int K; 
        cin >> str >> K;
        int n = strlen(str);
        memset(cnt, 0, sizeof(cnt));
        
        long long ans = 0;
        int j = -1;
        for (int i = 0; i < n; ++i) {
            while (j + 1 < n && distinct() < K) {
                ++j;
                ++cnt[str[j] - 'a'];
            }
            if (distinct() < K) break; // 剩餘子串都不合法
            ans = (ans + n - j) % MOD;
            --cnt[str[i] - 'a']; // 移動左端點
        }
        cout << ans << '\n';
    }
    return 0;
}

易錯點提醒

1. j 初始化為 -1，進入循環先 ++j，避免邊界錯誤。
2. 內層 while 條件用 distinct() < K 而非 !=，確保找到「至少 K 種」的最小 j。
3. 若遍歷完 j 仍不足 K 種，後續 i 更不可能，直接 break。