Longest Substring with At Most Two Distinct Characters
Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”,
T is "ece" which its length is 3.
Two pointers, Hash table
public int lengthOfLongestSubstringTwoDistinct(String s) {
if(s == null || s.length() == 0)
return 0;
Map<Character, Integer> map = new HashMap<>();
int b = 0, e = 0, max = 1;
while(e < s.length()){
char ce = s.charAt(e);
map.put(ce, map.getOrDefault(ce, 0) + 1);
while(map.size() > 2){
char cb = s.charAt(b);
int amount = map.get(cb);
if(-- amount > 0){
map.put(cb, amount);
}else map.remove(cb);
b ++;
}
max = Math.max(max, e - b + 1);
e ++;
}
return max;
}
K Distinct Characters
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if(s == null || s.length() == 0 || k == 0)
return 0;
Map<Character, Integer> map = new HashMap<>();
int b = 0, e = 0, max = 1;
while(e < s.length()){
char ce = s.charAt(e);
map.put(ce, map.getOrDefault(ce, 0) + 1);
while(map.size() > k){
char cb = s.charAt(b);
int amount = map.get(cb);
if(-- amount > 0){
map.put(cb, amount);
}else map.remove(cb);
b ++;
}
max = Math.max(max, e - b + 1);
e ++;
}
return max;
}