340. Longest Substring with At Most K Distinct Characters

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

For example, Given s = “eceba” and k = 2,

T is "ece" which its length is 3.

一刷
解法同159， 就是用一个map存character, index. 保证map的size小于k, 否则，寻找map中entry拥有最小的value。但是有更快的方法，比如有序的map. 留给二刷

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if(k == 0 || s == null || s.length()==0) return 0;
        int res = 0;
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, right = 0;
        for(int i=0; i<s.length(); i++){
            char ch = s.charAt(i);
            if(map.size()<k || map.containsKey(ch)){
                map.put(ch, i);
                res = Math.max(res, i-left+1);
            }else{
                //find the minimum in the map
                int value = Integer.MAX_VALUE;
                char key = 'a';
                for(Map.Entry<Character, Integer> entry : map.entrySet()){
                    if(entry.getValue()<value) {
                        value = entry.getValue();
                        key = entry.getKey();
                    }
                }
                map.remove(key);
                map.put(ch, i);
                left = value+1;
                res = Math.max(res, i-left+1);
            }
        }
        return res;
    }
}

二刷
词频统计array, sliding window
如果是该char第一次出现，count++
如果count>k, 那么从start开始remove, 如果remove后，词频数组显示这个ch没有出现，那么count--, 直到count==k

class Solution {
    // Solution 1: two pointer
    // Solution 2: TreeMap<>. dealing with stream input
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        char[] arr = s.toCharArray();
        int[] table = new int[256];
        int start = 0;
        int maxLen = 0;
        int count = 0;
        for(int end = 0; end < arr.length; end++) {
            if(table[arr[end]]++ == 0) {
                count++;
                while(count > k) {
                    if(--table[arr[start++]] == 0) {
                        count--;
                    }
                }
            }
            maxLen = Math.max(maxLen, end - start + 1);
        }
        return maxLen;
    }
}