Longest Substring With At Most K Distinct Characters
Longest Substring With At Most K Distinct Characters string
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.
Longest Substring With At Most K Distinct Characters Solution
public class LongestSubstringWithAtMostKDistinctCharacters {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int[] count = new int[256]; // there are 256 ASCII characters in the world
int i = 0; // i will be behind j
int num = 0;
int res = 0;
for (int j = 0; j < s.length(); j++) {
if (count[s.charAt(j)] == 0) { // if count[s.charAt(j)] == 0, we know that it is a distinct character
num++;
}
count[s.charAt(j)]++;
while (num > k && i < s.length()) { // sliding window
count[s.charAt(i)]--;
if (count[s.charAt(i)] == 0){
num--;
}
i++;
}
res = Math.max(res, j - i + 1);
}
return res;
}
}
Last modified October 4, 2020