Longest Substring with At Most K Distinct Characters
lc 340 Given a string S, find the length of the longest substring T that contains at most k distinct characters.
Input: S = "eceba" and k = 3
Output: 4
Explanation: T = "eceb"
public class Solution {
/**
* @param s: A string
* @param k: An integer
* @return: An integer
*/
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s == null || s.length() == 0 || k == 0) return 0;
int start = 0;
int end = 0;
int res = 0;
Map<Character, Integer> charToCount = new HashMap<>();
for (start = 0; start < s.length(); start++) {
while(end < s.length()) {
if (charToCount.containsKey(s.charAt(end))) {
int count = charToCount.get(s.charAt(end));
charToCount.put(s.charAt(end), charToCount.get(s.charAt(end))+ 1);
} else {
if (charToCount.size() != k) {
charToCount.put(s.charAt(end), 1);
} else {
break;
}
}
end++;
}
res = Math.max(res, end - start);
if (end == s.length()) {
break;
}
if (charToCount.containsKey(s.charAt(start))) {
int count = charToCount.get(s.charAt(start)) - 1;
if (count == 0) {
charToCount.remove(s.charAt(start));
} else {
charToCount.put(s.charAt(start), count);
}
}
}
return res;
}
}