Substring with At Least K Distinct Characters

Given a string S with only lowercase characters.

Return the number of substrings that contains at least k distinct characters.

Example

Example 1:

Input: S = "abcabcabca", k = 4
Output: 0
Explanation: There are only three distinct characters in the string.

Example 2:

Input: S = "abcabcabcabc", k = 3
Output: 55
Explanation: Any substring whose length is not smaller than 3 contains a, b, c.
    For example, there are 10 substrings whose length are 3, "abc", "bca", "cab" ... "abc"
    There are 9 substrings whose length are 4, "abca", "bcab", "cabc" ... "cabc"
    ...
    There is 1 substring whose length is 12, "abcabcabcabc"
    So the answer is 1 + 2 + ... + 10 = 55.

Notice

1. 10 ≤ length(S) ≤ 1,000,000
2. 1 ≤ k ≤ 26

思路：固定左边界i， 然后每次去判断i以后的substring，用hashmap去统计j走到的位置的distinct characters.

然后count += s.length() - 1 - (j-1) + 1 = s.length() - j + 1.因为j是到了满足hashmap.size() == k的下一个位置；然后i需要move，更新hashmap即可，下次循环再继续判断i,j之间的substring；

注意count is long type.

public class Solution {
    /**
     * @param s: a string
     * @param k: an integer
     * @return: the number of substrings there are that contain at least k distinct characters
     */
    public long kDistinctCharacters(String s, int k) {
        if(s == null || s.length() == 0 || k <=0 ) {
            return 0;
        }
        
        HashMap<Character, Integer> hashmap = new HashMap<Character, Integer>();
        long count = 0;
        int j = 0;
        for(int i = 0; i < s.length(); i++) {
            while(j < s.length() && hashmap.size() < k){
                char jc = s.charAt(j);
                if(hashmap.containsKey(jc)){
                    hashmap.put(jc, hashmap.get(jc) + 1);
                } else {
                    hashmap.put(jc, 1);
                }
                j++;
            }
            
            if(hashmap.size() == k) {
                count += s.length() - j + 1;
            }
            
            char ic = s.charAt(i);
            if(hashmap.containsKey(ic)){
                if(hashmap.get(ic) > 1){
                    hashmap.put(ic, hashmap.get(ic) - 1);
                } else {
                    hashmap.remove(ic);
                }
            }
        }
        return count;
    }
}