Longest Substring with At Most K Distinct Characters

LeetCode Q 386 - Longest Substring with At Most K Distinct Characters

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

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"
Challenge : O(n) time

Similar Question: Longest Substring Without Repeating Characters, Minimum Window Substring, Find All Anagrams in a String

Solution

Sliding Window: Time Complexity: O(n)

Method 1: Use an array

Code:

public int lengthOfLongestSubstringKDistinct(String s, int k) {
	if (s == null || s.length() == 0 || k == 0) return 0;
	if (s.length() <= k) return s.length();
	int[] count = new int[256];
	int l = 0, r = 0, distNum = 0, maxLen = 0;;
	while (r < s.length()) {
		if (count[s.charAt(j)] == 0) distNum++;
		count[s.charAt(j++)]++;
		while (distNum > k) {
			if (count[s.charAt(i)] == 1) distNum--;
			count[s.charAt(i++)]--;
		}
		maxLen = Math.max(maxLen, j - i);
	}
	return maxLen;
}

Method 2: Use an hashmap

Code:

public int lengthOfLongestSubstringKDistinct(String s, int k) {
	if(s==null || s.length()==0) return 0;
	
	//store char and number of occurance. 
	HashMap<Character, Integer> map = new HashMap<>();
	
	int len = 0, counter = 0;
	for(int start = 0, end = 0; end < s.length(); end++) {
		char curr = s.charAt(end);
		if (map.get(curr) == null) map.put(curr, 0);
		map.put(curr, map.get(curr) + 1);
		if(map.get(curr)==1) counter++;
		
		//check size of k in current window
		while(counter > k) {
			char first = s.charAt(start);
			map.put(first, map.get(first)-1);
			if(map.get(first) == 0) counter--;
			start++;
		}
		len = Math.max(len, end-start+1);
	}
	return len;
}