03 Longest Substring with K Distinct Characters (medium) √

最多有K个不同字符的最长子串

Problem Statement

Given a string, find the length of the longest substring in it with no more than **K** distinct characters.

Example 1:

Input: String="araaci", K=2 Output: 4 Explanation: The longest substring with no more than '2' distinct characters is "araa".

Example 2:

Input: String="araaci", K=1 Output: 2 Explanation: The longest substring with no more than '1' distinct characters is "aa".

Example 3:

Input: String="cbbebi", K=3 Output: 5 Explanation: The longest substrings with no more than '3' distinct characters are "cbbeb" & "bbebi".

Example 4:

Input: String="cbbebi", K=10 Output: 6 Explanation: The longest substring with no more than '10' distinct characters is "cbbebi".

    public static int findLength(String str, int k) {
        // use a hashmap to record the current amount of distinct characters
        HashMap<Character, Integer> map = new HashMap<>(k);
        int sum = 0;
        char[] chars = str.toCharArray();
        int start = 0;
        int result = Integer.MIN_VALUE;
        for(int i = 0; i < chars.length; i++){
            if(map.getOrDefault(chars[i], 0) == 0) {
                sum++;
            }
            map.put(chars[i],map.getOrDefault(chars[i], 0) + 1);
            while ( sum > k){
                map.put(chars[start],map.getOrDefault(chars[start], 0) -1);
                if(map.getOrDefault(chars[start], 0) == 0){
                    sum--;
                }
                start++;
            }
            if (sum <= k) {
               result = Math.max(result, i - start + 1);
            }
        }
        return result != Integer.MIN_VALUE ? result : -1;
    }