Poison

340. Longest Substring with At Most K Distinct Characters

Sliding Window
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
// 注意 k 可能等于 0, 会触发后续 Collections.min 中的异常,所以提前检查
if (s.length() * k == 0) {
return 0;
}

Map<Character, Integer> charToLastIndexMap = new HashMap<>();

// subString: (i, j]
int i = -1, maxLength = 0;
for (int j = 0; j < s.length(); j++) {
char c = s.charAt(j);
if (charToLastIndexMap.size() == k && !charToLastIndexMap.containsKey(c)) {
// 出现了第 k + 1 个不同字符,需要校正 i 的下标
i = Collections.min(charToLastIndexMap.values());
charToLastIndexMap.remove(s.charAt(i));
}

maxLength = Math.max(maxLength, j - i);
charToLastIndexMap.put(c, j);
}

return maxLength;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
// 注意 k 可能等于 0, 会触发异常,所以提前检查
if (s.length() * k == 0) {
return 0;
}

Map<Character, Integer> charToLastIndexMap = new LinkedHashMap<>();

// subString: (i, j]
int i = -1, maxLength = 0;
for (int j = 0; j < s.length(); j++) {
char c = s.charAt(j);
if (charToLastIndexMap.size() == k && !charToLastIndexMap.containsKey(c)) {
// 出现了第 k + 1 个不同字符,需要校正 i 的下标
i = charToLastIndexMap.values().iterator().next();
charToLastIndexMap.remove(s.charAt(i));
}

maxLength = Math.max(maxLength, j - i);
charToLastIndexMap.remove(c);
charToLastIndexMap.put(c, j);
}

return maxLength;
}
}
Reference

340. Longest Substring with At Most K Distinct Characters