340. Longest Substring with At Most K Distinct Characters (sliding window, hashmap, two pointers),
159 is the same to this
Previous3. Longest Substring Without Repeating CharactersNext424. Longest Repeating Character Replacement
Last updated
159 is the same to this
Last updated
time: O(n)
space: O(1)
class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int max = 0;
int count[] = new int[256];
int num = 0; // record kind of chars
int j = 0; // left
for (int i = 0; i < s.length(); i++) {
if (count[s.charAt(i)] == 0) {
num++;
}
count[s.charAt(i)]++;
// left: j start to move k size windows,
// when j move, count[j]--, if 0 means, kind of char --
while (num > k && j < s.length()) {
count[s.charAt(j)]--;
if (count[s.charAt(j)] == 0) {
num--; // make k size windows fit to k
}
j++;
}
max = Math.max(max, i - j + 1);
}
return max;
}
}
/*
count[] record char count
num - how many different kind of char
int j = 0, left
"eceba"
j
i
count[e] = 2;
count[c] = 1; num = 2;
count[b] = 1; num = 3
if (num > k) { // maintain k size, let k size -1
while (count[j] > 0) {
count[j]--
j++
}
}
max = i - j +1 = 3
*/
```java
class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int n = s.length();
int left = 0;
int result = 0;
Map<Character, Integer> freqMap = new HashMap<>();
for (int right = 0; right < n; right++) {
char rightChar = s.charAt(right);
freqMap.put(rightChar, freqMap.getOrDefault(rightChar, 0)+1);
while (left <= right && freqMap.size() > k) {
char leftChar = s.charAt(left);
freqMap.put(leftChar, freqMap.getOrDefault(leftChar, 0)-1);
if (freqMap.get(leftChar) == 0) {
freqMap.remove(leftChar);
}
left++;
}
result = Math.max(result, right - left + 1);
}
return result;
}
}
/**
at most k
> k
left++
abee
*/
```