LeetCode 340. Longest Substring with At Most K Distinct Characters

Question

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-char

• Solution1

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, res = 0;
        for (int i = 0; i < s.length(); i++){
            char cur = s.charAt(i);
            map.put(cur, map.getOrDefault(cur, 0) + 1);
            while (map.size() > k){
                char c = s.charAt(left);
                map.put(c, map.get(c) - 1);
                if (map.get(c) == 0) map.remove(c);
                left++;
            }
            res = Math.max(res, i - left + 1);
        }
        return res;
    }
}

Complexity:

Time complexity: O( n)

Space complexity: O(n)