Longest Substring with At Most K Distinct Characters

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

Example

Example 1:

Input: S = "eceba" and k = 3
Output: 4
Explanation: T = "eceb"

Example 2:

Input: S = "WORLD" and k = 4
Output: 4
Explanation: T = "WORL" or "ORLD"

Challenge

O(n) time

class Solution {
    public int lengthOfLongestSubstringKDistinct(String str, int k) {
        if (k == 0 || str.length() == 0)
            return 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int start = 0, unique = 0;
        int maxLen = 0;
        for (int i = 0; i < str.length(); i++) {
            char x = str.charAt(i);
            if (!map.containsKey(x) || map.get(x) == 0)
                unique++;
            map.put(x, map.getOrDefault(x, 0) + 1);
            // Removing characters from start of our window until the number
            // of unique chars > K
            while (unique > k) {
                map.put(str.charAt(start), map.get(str.charAt(start)) - 1);
                if (map.get(str.charAt(start)) == 0) {
                    map.remove(str.charAt(start));
                    unique--;
                }
                start++;
            }
            maxLen = Math.max(maxLen, i - start + 1);
        }
        return maxLen;
    }
}