【Lintcode】1375. Substring With At Least K Distinct Characters

题目地址：

https://www.lintcode.com/problem/substring-with-at-least-k-distinct-characters/description

给定一个字符串 s s s，求其包含至少 k k k个不同字符的子串的个数。

思路是双指针。开两个指针 i i i和 j j j，其中 i i i是右指针， j j j是左指针。我们累加以 j j j为左端点的满足条件的子串个数。当 s [ j : i ] s[j:i] s[j:i]这个区间里包含至少 k k k个不同字符时，此时 ∀ k ≥ i , s [ j : k ] \forall k \ge i, s[j:k] ∀k≥i,s[j:k]都成立，所以累加 l s − i l_s-i ls​−i，此时左端点为 j j j的情况已经枚举完毕，则右移 j j j，继续做累加，直到区间不满足条件为止，则右移 i i i。代码如下：

import java.util.HashMap;
import java.util.Map;

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
        Map<Character, Integer> map = new HashMap<>();
        
        long res = 0;
        for (int i = 0, j = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
            
            while (map.size() >= k) {
                res += s.length() - i;
                
                char ch = s.charAt(j);
                map.put(ch, map.get(ch) - 1);
                if (map.get(ch) == 0) {
                    map.remove(ch);
                }
                
                j++;
            }
        }
        
        return res;
    }
}

时空复杂度 O ( l s ) O(l_s) O(ls​)。