A slightly different C++ solution with comments


  • 0
    N

    Here, the hash table is used to store the last position of a char that is in the current longest substring.

    class Solution {
        public:
            int lengthOfLongestSubstringKDistinct(string s, int k) {
                if(k == 0 ) return 0;
                unordered_map <char, int> hash;  // store the last position of a char
                int count = 0, ret = 0;
                
                for(int i = 0; i < s.length(); i++){
                    if(hash.find(s[i]) != hash.end() || hash.size() < k){   // either already appeared, or still have less than k chars
                        hash[s[i]] = i;    // update the last position to be here
                        count ++;
                    }
                    else{
                        int ind = i - count;            // the beginning of previous longest
                        while(hash[s[ind]] != ind)      // find where to cut 
                            ind ++; 
                        hash.erase(s[ind]);             // update hash table
                        count = i - ind;
                        hash[s[i]] = i;
                    }
                    
                    ret = max(ret, count);
                    
                }
                
                return ret;
            }
        };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.