【Lintcode】1375. Substring With At Least K Distinct Characters
程序员文章站
2024-03-06 21:25:50
...
题目地址:
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)。
上一篇: Spring实现IoC的多种方式小结