Leetcode: 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.

Understand the problem:
The problem is very similar to the Leetcode question 3 (Longest Substring Without Repeating Characters). 

The key idea of the solution is to use two pointers to maintain a "sliding window". We also use a HashMap to store all the characters in the window. Each time we move forward the "start" pointer and increase the size of the sliding window until the size of the window is greater than K. Then we can easily calculate the size of the window which contains at most K distinct characters. The next step is to shrink the window by moving forward the "end" pointer. In order to get the maximum window size, we must move the minimum steps of the end pointer. So each step we move the end pointer, we need to update the map and remove the character out of the sliding window. The stop condition is that when the window size is again equal to the K, which means the window contains K distinct characters. That's the minimum steps we need to move forward the end pointer. 

The only trick here is we need to check at the last that if the start pointer is out of boundary, we still need to check if the largest window size. That's a common trick for major string w/ two pointer problems.


Code (Java):

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k <= 0) {
            return 0;
        }
        
        Map<Character, Integer> map = new HashMap<>();
        int i = 0;
        int j = 0;
        int maxLen = 0;
        
        for (i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                int freq = map.get(c);
                map.put(c, freq + 1);
            } else {
                map.put(c, 1);
            }
            
            if (map.size() > k) {
                maxLen = Math.max(maxLen, i - j);
            
                // Shrink the window size
                while (map.size() > k) {
                    char endC = s.charAt(j);
                    int freq = map.get(endC);
                    if (freq == 1) {
                        map.remove(endC);
                    } else {
                        map.put(endC, freq - 1);
                    }
                    j++;
                }
            }
        }
        
        if (j < s.length()) {
            maxLen = Math.max(maxLen, i - j);
        }
        
        return maxLen;
    }
}

Analysis:
Time complexity: O(n)
Space complexity O(k)

Update on 1/6/2021

public class Solution {
    /**
     * @param s: A string
     * @param k: An integer
     * @return: An integer
     */
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        // write your code here
        if (s == null || s.length() == 0 || k <= 0) {
            return 0;
        }
        
        int[] countArr = new int[256];
        int count = 0;
        
        int left = 0;
        int right = 0;
        int maxLen = 0;
        
        for (right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (countArr[c] == 0) {
                count++;
            }
            
            countArr[c]++;
            
            // update the answer
            if (count <= k) {
                maxLen = Math.max(maxLen, right - left + 1);
            }
            
            // move the left pointer if necessary 
            while (count > k) {
                char leftChar = s.charAt(left);
                countArr[leftChar]--;
                
                if (countArr[leftChar] == 0) {
                    count--;
                }
                
                left++;
            }
        }
        
        return maxLen;
    }
}