340. Longest Substring with At Most K Distinct Characters 发表于 2022-02-08 Sliding Window1234567891011121314151617181920212223242526class 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; }} 123456789101112131415161718192021222324252627class 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; }} Reference340. Longest Substring with At Most K Distinct Characters