340. Longest Substring with At Most K Distinct Characters

340.HashMap.java

    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map<Character, Integer> map = new HashMap<>();
        if (s == null || s.length() == 0 || k == 0) return 0;
        int start = 0;
        int longest = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i)) || map.size() < k) {
                map.put(s.charAt(i), i);
            } else {
                int minPos = getMinPos(map);
                start = minPos + 1;
                map.put(s.charAt(i), i);
            }
            longest = Math.max(longest, i - start + 1);
        }
        return longest;
    }
    private int getMinPos(Map<Character, Integer> map) {
        Map.Entry<Character, Integer> result = null;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (result == null || entry.getValue() < result.getValue()) {
                result = entry;
            } 
        }
        map.remove(result.getKey());
        return result.getValue();
    }

340.TwoPointers.java

/**
follow up: How about stream input (infinite input) 用Mapreduce
follow upup: Any other solution？ KMP
*/

	public int lengthOfLongestSubstringKDistinct(String s, int k) {
  		if(s.length() == 0 || k == 0) return 0;

  		int[] letters = new int[128];
  		int count = 0, i = 0, j = 0, max = 0;

  		while(j < s.length()) {
	  		if(++letters[s.charAt(j)] == 1) count++;
	  		while(count > k) {
		  		if(--letters[s.charAt(i)] == 0) count--;
		  		i++;
	  		}
	  		max = Math.max(max, j-i+1);

	  		j++;
  		}
  		return max;
	}