340. Longest Substring with At Most K Distinct Characters

這是一個我覺得蠻好的滑動窗口題目, 我們先用一個table紀錄每個字母出現以及他的次數, 然後當table裡的數字超過k個, 我們便移動left直到table可以刪掉其中一個字母, 接著紀錄最長的長度即可, 時間複雜度為O(n)

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int left = 0;
        unordered_map<char, int> m;
        int maxLen = 0;
        for(int i = 0; i < s.size(); i++){
            m[s[i]]++;
            while(m.size() > k){
                m[s[left]]--;
                if(m[s[left]] == 0){
                    m.erase(s[left]);
                }
                left++;
            }
            maxLen = max(maxLen, i - left + 1 );
        }
        return maxLen;
    }
};