Leetcode Everyday: 340. Longest Substring with At Most K Distinct Characters
1335 ワード
https://leetcode.com/problems/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 =
T is "ece"which its length is 3
occurrence is from 1->0, this means a char has been removed out of the window.
asd
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
public class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if(k==0) return 0;
char[] cArr = s.toCharArray();
int[] occ = new int[128];
int start = 0;
int dis = 0;
int maxLen = 0;
for(int i = 0; ik){
while(--occ[cArr[start++]] != 0);
}
}else{
occ[cArr[i]]++;
}
if(i-start+1>maxLen) maxLen = i-start+1;
}
return maxLen;
}
}
The idea is to keep a sliding window using two pointers. The first pointer is start, and the second pointer is i. we record how many times does a char occurs in the window. When we encounter a new char and there are k+1 chars in the window, we increase the start pointer and make correspond changes in the occurrence array, util we find some chars occurrence is from 1->0, this means a char has been removed out of the window.
asd