340 - Longest Substring With At Most K Distinct Characters 最多有K個不同字符的最長子串

#hard

Given a string, find the length of the longest substring T that contains at most k distinct characters.

Example 1:
Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.

Example 2:
Input: s = "aa", k = 1
Output: 2
Explanation: T is "aa" which its length is 2.

1. sliding window + hashtable的組合技
2. 不能用set的原因: 因為subarray中可能有duplicate character，要確認subarray出現的元素都沒出現，才從hashtable刪除。

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]] ++;

      // table.size() > k 表示有超過 k 個 distinct character
      while(table.size() > k) {
        if(--table[s[windowStart]] == 0)
          table.erase(s[windowStart]);

        windowStart++;
      }

      // 經過上面的 while 迴圈處理，這時 window 必定滿足條件
      maxLength = max(maxLength, windowEnd-windowStart+1);
    }

    return maxLength;
  }
};