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) {
        // Write your code here


        int[] char_count = new int[26];

        long count_result = 0; // attention: use long data type here
        long count_unique_char = 0;
        int i_left = 0;
        int i_right = -1;

        char c_now;
        int i_now;

        while (true) {
            if (i_right == s.length()) break;
            if (i_left == s.length()) break;

            if (count_unique_char < k) {
                // not enough characters yet
                // collect char
                i_right++;
                if (i_right == s.length()) break; // attention
                c_now = s.charAt(i_right);
                i_now = c_now - 'a';


                if (char_count[i_now] == 0) {
                    // new char inserted
                    count_unique_char++;
                }

                char_count[i_now]++;
            }else {
                // enough characters
                count_result += (s.length() - i_right); // find answer area

                // remove the left most to see if any better in the future
                c_now = s.charAt(i_left);
                i_now = c_now - 'a';
                char_count[i_now]--;
                if (char_count[i_now] == 0) {
                    // the last char is remove for this one
                    count_unique_char--;
                }

                i_left++;
            }

        } // end of while

        return count_result;
    }
}