HDU 5056：雙指針/滑動窗口統計合法子串

題目大意

• 給定小寫字母串 S（長度 ≤ 100,000）和整數 K。
• 求子串個數，使得子串中每個字母出現次數 ≤ K。
• 多測試用例 T ≤ 100。

滑動窗口（雙指針）O(n) 解法

1. 維護窗口 [L, R] 內字母計數 `cnt[26]`。
2. 右指針 `R` 逐步右擴，加入 `S[R]`。
3. 若某字母計數超過 `K`，則左指針 `L` 右移並減少計數，直到窗口再次合法。
4. 對每個 `R`，以 `R` 為右端點的合法子串數 = `R - L + 1`，累加到答案。

完整代碼

#include 
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        string s; int K;
        cin >> s >> K;
        int n = s.size();
        vector cnt(26, 0);
        ll ans = 0;
        int L = 0;
        for (int R = 0; R < n; ++R) {
            int c = s[R] - 'a';
            ++cnt[c];
            while (cnt[c] > K) {
                --cnt[s[L] - 'a'];
                ++L;
            }
            ans += R - L + 1;
        }
        cout << ans << "\n";
    }
    return 0;
}

範例驗證

S = "abcabc", K = 1
R=0: [a] cnt[a]=1 OK ans+=1
R=1: [a,b] ans+=2 (ab,b)
R=2: [a,b,c] ans+=3
R=3: add a -> cnt[a]=2 >1 => L=1 remove a cnt[a]=1 => window [b,c,a] ans+=3
R=4: add b -> cnt[b]=2 >1 => L=2 remove b => [c,a,b] ans+=3
R=5: add c -> cnt[c]=2 >1 => L=3 remove c => [a,b,c] ans+=3
Total = 1+2+3+3+3+3 = 15 ✓

複雜度

• 每個字符進出窗口各一次：O(n)。
• 空間 O(1)（26 字母計數）。