159/340. Longest Substring with At Most Two/K Distinct Characters

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

For example, Given s =“eceba”,

T is "ece" which its length is 3.

Solution:

• Using hash map to track character and the how many times it has appeared
• traverse with right pointer from 0 to the end of the string
  • when the current character is not in the map, update the map, update the k
    • if k >= 0, update the max length, current len = current i -left +1
    • if k < 0, update the max length, current len = current i - left (only allowed to the position before current i)
    • while k < 0
      • keep remove the most left element, update the hash map and k
  • when the current is in the map, update the map, and max len, current length = current i - left + 1

public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if(s == null || s.length() == 0){
            return 0;
        }
        Map<Character, Integer> hm = new HashMap<>();

        int cnt = k;
        int len = Integer.MIN_VALUE;
        int left = 0;
        char[] arr = s.toCharArray();

        for(int right = 0; right < s.length(); right++){
            if(!hm.containsKey(arr[right])){
                hm.put(arr[right], 1);
                cnt--;
                if(cnt >= 0){
                    len = Math.max(len, right - left + 1);
                }else{
                    len = Math.max(len, right - left);

                    while(cnt < 0){
                        if(hm.containsKey(arr[left])){
                            hm.put(arr[left], hm.get(arr[left]) - 1);
                            if(hm.get(arr[left]) == 0){
                                hm.remove(arr[left]);
                                cnt++;
                            }
                            left++;
                        }
                    }
                }  

            }else{
                hm.put(arr[right], hm.get(arr[right])+ 1);
                len = Math.max(len, right - left + 1);
            }


        }
        if(len > s.length()){
            return 0;
        }else{
            return len;
        }    
    }