340. Longest Substring with At Most K Distinct Characters

340. Longest Substring with At Most K Distinct Characters

Question

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.

Solutions

• Method 1: Sliding window + HashMap

  class Solution {
        public int lengthOfLongestSubstringKDistinct(String s, int k) {
            if(s.length() <= k) return s.length();
            int start = 0, end = 0;
            Map<Character, Integer> map = new HashMap<>();
            char[] arr = s.toCharArray();
            int max = 0;
            while(end < s.length()){
                if(map.containsKey(arr[end]) || map.size() < k){
                    map.put(arr[end], map.getOrDefault(arr[end], 0) + 1);
                    max = Math.max(max, end - start + 1);
                }else{  // current we need to remove
                    map.put(arr[end], 1);
                    while(map.size() > k){
                        char c = arr[start++];
                        int count = map.get(c);
                        if(count == 1){
                            map.remove(c);
                        }else{
                            map.put(c, count - 1);
                        }
                    }
                }
                end++;
            }
            return max;
        }
    }