340. Longest Substring with At Most K Distinct Characters

Given a string, find the length of the longest substring T that contains at mostkdistinct 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.

Thoughts:

1. keep tracking the size char hashtable d, if oversized, pull the least index value from it and delete the entry, update the low index.

2. each step compare the current min with (i - low + 1)

Code:

class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        d, low, ans = {}, 0, 0

        for i,c in enumerate(s) :
            d[c] = i
            if len(d) > k:
                low = min(d.values())
                del d[s[low]]
                low += 1
            ans = max(i - low + 1, ans)
        return ans

Code: C++ Template

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        vector<int> map (128, 0);
        int slow = 0, fast = 0, d = 0, cnt = 0;
        while (fast < s.size()){
            if(map[s[fast++]]++ == 0) cnt++;
            while(cnt == k + 1) if(map[s[slow++]]-- == 1) cnt--; // or cnt > k
            d = max(d, fast - slow);
        }

        return d;
    }
};