Lintcode 1375 Substring With At Least K Distinct Characters
https://www.lintcode.com/problem/1375
Given a string S with only lowercase characters.
Return the number of substrings that contains at least k distinct characters.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.This problem can also use the two pointers method we talked about in https://leetcode-solution.com/leetcode-209-minimum-size-subarray-sum-2/ with time complexity of O(n)
The idea is the same, iterate the left pointer, at each iteration, find the right pointer so that the subarray has k distinct characters. But there is on tricky part here, once we found a right pointer, all the indices after the right point will also meet the requirement. So instead of increase the final result by 1, we should also consider adding however many indices after the right pointer.
Now let’s take a look at the solution
export class Solution {
/**
* @param s: a string
* @param k: an integer
* @return: the number of substrings there are that contain at least k distinct characters
*/
kDistinctCharacters(s, k) {
let right = 0;
let result = 0;
let charToCount = {};
let distinctCharCount = 0;
for(let left = 0; left < s.length; left++) {
while(right < s.length && distinctCharCount < k) {
if(charToCount[s[right]]) {
charToCount[s[right]] += 1
} else {
charToCount[s[right]] = 1
distinctCharCount++;
}
right++;
}
if(distinctCharCount === k) {
result += s.length - right + 1;
}
charToCount[s[left]]--;
if(charToCount[s[left]] === 0) {
distinctCharCount--;
}
}
return result;
}
}