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;
    }
}

References

340. Longest Substring with At Most K Distinct Characters