欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Substring with At Least K Distinct Characters

程序员文章站 2022-03-11 21:49:45
...

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;
    }
}

 

相关标签: Two pointers