双指针,窗口类
这两题有一个 trick 和 Minimum Window Substring 非常像,就是维护一个 "curCount" 代表目前 (i,j) 之间 match 上的数量,而通过 hash[] 的正负充当计数器的作用。
public class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
int maxSize = 0;
int j = 0;
int[] hash = new int[256];
int distinctCount = 0;
for(int i = 0; i < s.length(); i++){
while(j < s.length()){
if(distinctCount == 2 && hash[s.charAt(j)] == 0) break;
if(hash[s.charAt(j)] == 0) distinctCount ++;
hash[s.charAt(j++)]++;
}
if(j - i > maxSize){
maxSize = j - i;
}
hash[s.charAt(i)]--;
if(hash[s.charAt(i)] == 0) distinctCount --;
}
return maxSize;
}
}
和上一题代码完全没有区别,只是把判断条件里面的 count 数字改一下而已。。
public class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int curCount = 0;
int j = 0;
int maxSize = 0;
int[] hash = new int[256];
for(int i = 0; i < s.length(); i++){
while(j < s.length()){
if(curCount == k && hash[s.charAt(j)] == 0) break;
if(hash[s.charAt(j)] == 0) curCount ++;
hash[s.charAt(j++)]++;
}
if(j - i > maxSize){
maxSize = j - i;
}
hash[s.charAt(i)]--;
if(hash[s.charAt(i)] == 0) curCount --;
}
return maxSize;
}
}
Last updated
Was this helpful?