class Solution {
public:
    /**
     * @param s : A string
     * @return : The length of the longest substring 
     *           that contains at most k distinct characters.
     */
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        // write your code here
        if (s.length() <= k) {
            return s.length();
        }

        int start = 0;
        int end = 0;

        int maxLen = INT_MIN;

        unordered_map<char, int> count;

        for (start = 0; start < s.length(); start++) {
            while (end < s.length()) {
                if (count.find(s[end]) != count.end()) {
                    count[s[end]]++;
                } else {
                    if (count.size() == k) {
                        break;
                    } else {
                        count.insert({s[end], 1});
                    }
                }
                end++;
            }

            maxLen = max(maxLen, end - start);

            if (count.find(s[start]) != count.end()) {
                if (count[s[start]] > 1) {
                    count[s[start]]--;
                } else {
                    count.erase(s[start]);
                }
            }
        }

        return maxLen;
    }
};