340. Longest Substring with At Most K Distinct Characters

Given a string, find the length of the longest substring T that contains at most k distinct characters.
For example, Given s = “eceba” and k = 2, T is "ece" which its length is 3.


int lengthOfLongestSubstringKDistinct(string s, int k){
  if(k == 0 || s.length() == 0) return 0;
  vector<int> dict(256, 0);
  int count = 0, maxLength = 0, start = 0;
  for(int i = 0; i < s.length(); i++){
    dict[s[i]]++;
    if(i == 0 || s[i] == s[i-1] || count < k) {
      if(dict[s[i]] == 1) count++;
      continue;
    }
    // k+1 distinctive char
    if((count == k && dict[s[i]] == 1)){
      maxLength = max(maxLength,i-start);
      while(start <= i){
        dict[s[start]]--;
        if(dict[s[start]] == 0) break;
        start++;
      }
      start++;
    }
  }
  return maxLength > (s.length() - start) ? maxLength : s.length() - start;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容