340. Longest-Substring-with-At-Most-K-Distinct-Characters

difficulty: Hard

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

Given a string, find the length of the longest substring T that contains at most k distinct characters.

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: T is "aa" which its length is 2.

Method One

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
​
        int size = 0;
        int max = 0;
        Map<Character, Integer> counts = new HashMap<>();

        char[] chars = s.toCharArray();
        int left = 0;

        for(int right = 0; right < s.length(); right++ ) {
            char c = chars[right];
            counts.put(c, counts.getOrDefault(c, 0) + 1);
            size += 1;
            while(counts.size() > k) {
                size -= 1;
                char last = chars[left++];
                counts.put(last, counts.get(last) - 1);
                if(counts.get(last) == 0) {
                    counts.remove(last);
                } 
            }
            max = Math.max(max, size);
        }
        return max;
    }
}
​