# 340 - Longest Substring with At Most K Distinct Characters

解法一 - Sliding Window

用 sliding window 會讓解法變得非常有效率,解法說明如下:

這邊之所以要用 Hash Table,而不是用 set 是因為要處理 window 裡有 duplicate char 的情況,例如,假設目前 window 是:

a, c, a, b

即使刪掉了 windowStart 的 a,後面還是有個 a,如果是用 set,我們就會以為刪掉了 windowStart 的 a 之後就沒有 a 了。

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int maxLength = 0, windowStart = 0;
        unordered_map<char, int> table;

        for(int windowEnd = 0; windowEnd<s.length(); windowEnd++) {
            table[s[windowEnd]] ++;

            while(table.size() > k) {
                if(--table[s[windowStart]]==0) 
                    table.erase(s[windowStart]);

                windowStart++;
            }

            maxLength = max(maxLength, windowEnd-windowStart+1);
        }

        return maxLength;
    }
};

Last updated