easy 9ms C++ solution with explanation


  • 0
    J
    class Solution {
    public:
        int lengthOfLongestSubstringKDistinct(string s, int k) {
            if (!k || s.empty()) return 0;
            
            int last_appear[256];
            for (int i=0; i<256; i++){
                last_appear[i] = -1;
            }
            
            int count = 0; // record how many distinct elements are in the window [i,j]
            
            int i=0, j=0;
            int longest = 0;
                         
            while (j<s.size()){
                // judge current window [i, j]
                // move j to next, if count<k || (s[j] is in the window)
                
                if (count<k || i<=last_appear[s[j]]){
                    longest = max(longest, j-i+1);
                    
                    // new element in the window
                    if (last_appear[s[j]]<i) count++;
                    
                    last_appear[s[j]] = j;
                    
                    j++;
                }
                // move i to next, if s[i] is a last one, count--
                else{
                    if (last_appear[s[i]]==i) count--;
                    i++;
                }
            }
            
            return longest;
        }
    };
    

Log in to reply
 

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