340. Longest Substring with At Most K Distinct Characters

/**
 * Sliding Window
 *
 * Time Complexity : O(N) - Each character is added and removed once.
 *
 * Space Complexity: O(k) - Map can grow to size k+1
 *
 * N = length of input string s
 *
 * Proof of Time Complexity:
 *
 * Suppose there are M distinct chars in input string, each char is repeating j
 * times on average. Thus total number of chars = M * j = N. Thus number of
 * operations:
 *
 * 1) To add into map = N,
 *
 * 2) M-k chars will be removed from map. thus (M-k)*j remove operations are
 * performed.
 *
 * Thus total operations = N + (M-k)*j. Here k is very small, thus total
 * operations = 2*N
 */
class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || k <= 0) {
            return 0;
        }
        if (s.length() <= k) {
            return s.length();
        }

        Map<Character, Integer> map = new HashMap();

        int start = 0;
        int end = 0;
        int maxLen = 0;
        int distinctCount = 0;

        while (end < s.length()) {
            char endChar = s.charAt(end);
            map.put(endChar, map.getOrDefault(endChar, 0) + 1);
            if (map.get(endChar) == 1) {
                distinctCount++;
            }
            end++;

            while (distinctCount > k) {
                char startChar = s.charAt(start);
                map.put(startChar, map.get(startChar) - 1);
                if (map.get(startChar) == 0) {
                    distinctCount--;
                }
                start++;
            }

            maxLen = Math.max(maxLen, end - start);
        }

        return maxLen;
    }
}