HDU 5672：String——雙指針統計至少含k種不同字符的子串數

題目大意

給定長度10~1,000,000的小寫字母串S，查詢包含至少k（1≤k≤26）種不同字符的子串數量。T≤10組測試。

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

維護窗口[l, r)內字符頻次cnt[26]及不同字符數diff。
對每個右端點r，擴展窗口直到diff ≥ k。此時以r為右端點的合法子串數 = n - r（因為進一步擴展右端點仍合法）。累加答案後，移動左端點l縮小窗口，更新cnt和diff，繼續尋找下一個合法窗口。

關鍵細節

• cnt[c]記錄字符出現次數（而非單純bool），移除左端點時僅當cnt[c]==1才diff--。
• 左端點移動後不重置右端點，保證總體O(n)。
• 答案可能達O(n^2)級，需long long（%lld）。
• 輸入字符串長度大，用scanf(\"%s\", s)讀取char陣列。

參考代碼 (C++)

= k) {
                ans += n - r;           // 所有以r為右端點的子串均合法
                if (--cnt[s[l]-'a'] == 0) --diff;
                ++l;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度分析

• 時間：O(n) per test case，雙指針各移動至多n次。
• 空間：O(n)存字符串 + O(1)輔助數組。

總結

經典「至少k種不同元素」子串計數問題，雙指針單調性完美適用。注意頻次數組而非布爾標記、左端點不回退、長長整型輸出三大細節。