lintcode 1375 · Substring With At Least K Distinct Characters

T: O(n)

S: O(1)

public class Solution {
    public long kDistinctCharacters(String s, int k) {
        int n = s.length();
        char[] uniqueMap = new char[26];
        int end = 0;
        int uniqueNum = 0; 
        long res = 0; // should long, data is too big, so the num of ways would be large
        for (int start = 0; start < n; start++) {
            while (end < n && uniqueNum < k) {
                uniqueMap[s.charAt(end)-'a']++;
                if (uniqueMap[s.charAt(end)-'a'] == 1) {
                    uniqueNum++;
                }
                end++;
            }
            if (uniqueNum == k) {
                res += (n - end + 1);
            }
            if (uniqueMap[s.charAt(start)-'a'] == 1) {
                uniqueNum--;
            }
            uniqueMap[s.charAt(start)-'a']--;

        }
        return res;
    }
}