Problem

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

Examples

Example 1:

Input: S = "eceba" and k = 3
Output: 4
Explanation: T = "eceb"

Example 2:

Input: S = "WORLD" and k = 4
Output: 4
Explanation: T = "WORL" or "ORLD"

Solution

Method 1 - Sliding Window

public int lengthOfLongestSubstringKDistinct(String s, int k) {
    int result = 0;
    int i=0;
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
 
    for(int j=0; j<s.length(); j++){
        char c = s.charAt(j);
        if(map.containsKey(c)){
            map.put(c, map.get(c)+1);
        }else{
            map.put(c, 1);
        }
 
        if(map.size()<=k){
            result = Math.max(result, j-i+1);
        }else{
            while(map.size()>k){
                char l = s.charAt(i);
                int count = map.get(l);
                if(count==1){
                    map.remove(l);
                }else{
                    map.put(l, map.get(l)-1);
                }
                i++;
            }
        }
 
    }
 
    return result;
}