340. Longest Substring with At Most K Distinct Characters

I implemented a naive code first. And of course, it doesn’t pass large test set.

1:  class Solution {  
2:  public:  
3:    int lengthOfLongestSubstringKDistinct(string s, int k) {  
4:      if (s.size() < k) return s.size();  
5:      int res = 0;  
6:      for (int i = 0; i < s.size(); i++) {  
7:        vector<int> letters(256, 0);  
8:        int count = 0;  
9:        int j = i;  
10:        while (j < s.size()) {  
11:          if (letters[s[j]] == 0) {  
12:            letters[s[j]] = 1;  
13:            count++;  
14:            if (count > k) break;  
15:          }  
16:          j++;  
17:        }  
18:        res = max(res, j-i);  
19:      }  
20:      return res;  
21:    }  
22:  };  

The top rated solution uses sliding window. Keep two pointers as the starting of the window and the end of the window. First of all, keep moving the right end of the window until the distinct characters are more than K. Then move the left end of the window until the distinct characters are equal to K. Then move right end again.

1:  class Solution {  
2:  public:  
3:    int lengthOfLongestSubstringKDistinct(string s, int k) {  
4:      int res = 0, j = -1, i = 0, distinct = 0;  
5:      vector<int> chars(256, 0);  
6:      for (; i < s.size(); i++) {  
7:        distinct += chars[s[i]]++ == 0;  
8:        while (distinct > k) {  
9:          distinct -= --chars[s[++j]] == 0;  
10:        }  
11:        res = max(res, i-j);  
12:      }  
13:      return res;  
14:    }  
15:  };