Lintcode 386: Longest Substring with At Most K Distinct Characters

https://www.lintcode.com/problem/longest-substring-with-at-most-k-distinct-characters/description

Notes:

This question is labeled as a hard question in Leetcode, but actually it is not that hard, many be a medium one.

The basic idea is to use a sliding window. When the total kinds of the letter is less than k, we just continue, and count both kind and number of each kind of letter. A hash map can do this.

When the number of kind is larger than k, we need to move the left side of the window, until the number of kind is no more larger than k. Then we can record the length of this valid string, and update the global maximum.

See the code below:

class Solution {
public:
    /**
     * @param s: A string
     * @param k: An integer
     * @return: An integer
     */
    int lengthOfLongestSubstringKDistinct(string &s, int k) {
        // write your code here
        int res = 0, left = 0, len = s.size(), ct = 0;
        if(!k) return res;
        unordered_map<char, int> mp;
        for(int i=0; i<len; ++i) {
            if(!mp.count(s[i]) || mp[s[i]] == 0) {
                ++ct;
                ++mp[s[i]];
                if(ct>k) {
                    while(ct>k) {
                        --mp[s[left++]];
                        if(mp[s[left-1]] == 0) --ct;
                    }
                }
            }
            else ++mp[s[i]];
            res = max(res, i - left + 1);
        }
        return res;
    }
};

Here is another way to write the code, which is shorter. But we need to erase element from a hash map. 

See the code blow:

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int res = 0, left = 0, len = tree.size();
        unordered_map<int, int> mp;
        for(int i=0; i<len; ++i) {
            ++mp[tree[i]];
            while(mp.size() > 2) {
                 if(--mp[tree[left]] == 0) mp.erase(tree[left]);
                 ++left;
            }
            res = max(res, i - left + 1);
        }
        return res;
    }
};

Now let us focus one the interesting part: what do the above two codes run in O(N)? It seems at some positions, we need to slide the left side of the window many times.

But if we look at the hash map, and it is clear that every element will be pushed in exactly once, and not every element (less than N) will be pop out. Thus, the total operate is less than 2N. So it is O(N).

[update: 12-07-2019] here is another version of code, which is more concise:

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string &s, int k) {
        int res = 0, left = 0, len = s.size(), ct = 0;
        if(!k) return res;
        unordered_map<char, int> mp;
        for(int i=0; i<len; ++i) {
            ++mp[s[i]];
            if(mp[s[i]] == 1) ++ct;
            while(ct>k) {
                --mp[s[left++]];
                if(mp[s[left-1]] == 0) --ct;
            }
            res = max(res, i - left + 1);
        }
        return res;
    }
};