340. Longest Substring with At Most K Distinct Characters

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map<Character, Integer> charCount = new HashMap<>();
        int left = 0, right = 0, distinct = 0, maxLength = 0;
        while (right < s.length()) {
            // Move right first.
            while (right < s.length() && distinct <= k) {
                if (!charCount.containsKey(s.charAt(right))) {
                    charCount.put(s.charAt(right), 0);
                    distinct += 1;
                }
                charCount.put(s.charAt(right), charCount.get(s.charAt(right)) + 1);
                right += 1;
            }

            // Get current Length and update maxLength if necessary
            if (distinct > k) {
                maxLength = Math.max(right - left - 1, maxLength);
            } else {
                maxLength = Math.max(right - left, maxLength);
                break;
            }

            // Move left
            while (distinct > k) {
                charCount.put(s.charAt(left), charCount.get(s.charAt(left)) - 1);
                if (charCount.get(s.charAt(left)) == 0) {
                    charCount.remove(s.charAt(left));
                    distinct -= 1;
                }
                left += 1;
            }
        }
        return maxLength;
    }
}

又是sliding window. 还是用sliding window的模板. 先移动右再移动左. 由于我们是求maximum, 因此在移动左前来取结果. 需要注意的是移动right的两个条件可能同时不满足, 即我们include完最后一个char后, distinct超过了k同时right此刻等于s.length(). 这个条件是我没想到的. 这点很关键. 以后解题时尽量让while循环的条件不超过两个. 然后思考两个条件是否能够同时不满足还是最多只能有一个不满足.

时间复杂度: O(n) 每个元素最多进入和被移除map一次.
空间复杂度: O(n) 因为使用了map.