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:

For example, Given s = "eceba", k = 3,

T is "eceb" which its length is 4.

Challenge:

O(n), n is the size of the string s.

Solution:

Similar to Longest Substring Without Repeating Characters, but we need to use a HashMap to store the count. We increase the counter when the character exists in HashMap and we add new character into HashMap when the size of HashMap is less than k. In the end of each iteration, we need to remove current character from HashMap if its count is zero, otherwise, we decrease its count.

Code:

public class Solution {
    /**
     * @param s : A string
     * @return : The length of the longest substring 
     *           that contains at most k distinct characters.
     */
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k == 0) {
            return 0;
        }
        int n = s.length();
        HashMap<Character, Integer> hmap = new HashMap<>();
        int j = 0;
        int len = 0;
        for (int i = 0; i < n; i++) {
            while (j < n) {
                char c = s.charAt(j);
                if (hmap.containsKey(c)) {
                    hmap.put(c, hmap.get(c) + 1);
                } else {
                    if (hmap.size() == k) {
                        break;
                    }
                    hmap.put(s.charAt(j), 0);
                }
                j++;
            }

            len = Math.max(len, j - i);
            if (hmap.get(s.charAt(i)) == 0) {
                hmap.remove(s.charAt(i));
            } else {
                hmap.put(s.charAt(i), hmap.get(s.charAt(i)) - 1);
            }
        }
        return len;
    }
}