Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.
(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)
Return the number of good subarrays of A.
Example 1:
Input: A = [1,2,1,2,3], K = 2 Output: 7 Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
Example 2:
Input: A = [1,2,1,3,4], K = 3 Output: 3 Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].
Note:
1 <= A.length <= 200001 <= A[i] <= A.length1 <= K <= A.length
Related Topics:
Hash Table, Two Pointers, Sliding Window
Similar Questions:
- Longest Substring Without Repeating Characters (Medium)
- Longest Substring with At Most Two Distinct Characters (Medium)
- Longest Substring with At Most K Distinct Characters (Hard)
Use [i, j) as a sliding window to find the maximum window which contains no more than K unique elements.
To achieve this, we use a map m to store the last position of each number in the current window.
When m.size() > K, we should move forward i to shrink the window until it become valid again.
When m.size() == K, [i, j) is the maximum window we are looking for.
Within this maximum window [i, j), there is a minimum window [k, j) containing no more than K unique elements. k is the minimal index in m.
Now, the number of valid subarrays in this window is k - i + 1.
Since k is monotonically increasing and must be no less than i, we can use k as a global pointer just like i and j so that the overall time complexity of moving k is O(N).
Whenever m.size() == K, we can move k forward until m[A[k] - '0'] == k, and add k - i + 1 to the answer.
// OJ: https://leetcode.com/problems/subarrays-with-k-different-integers/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
int subarraysWithKDistinct(vector<int>& A, int K) {
int ans = 0, i = 0, j = 0, k = 0, N = A.size();
unordered_map<int, int> m;
while (j < N) {
m[A[j] - '0'] = j;
++j;
while (m.size() > K) {
int d = A[i++] - '0';
if (m[d] < i) m.erase(d);
}
if (m.size() == K) {
k = max(i, k);
while (m[A[k] - '0'] != k) ++k;
ans += k - i + 1;
}
}
return ans;
}
};Check out "C++ Maximum Sliding Window Cheatsheet Template!" which can help you solve all sliding window problems.
We can turn this problem into two find maximum sliding window problem: one is to find a window with at most k different integers, another is to find a window with at most k - 1 different integers.
// OJ: https://leetcode.com/problems/subarrays-with-k-different-integers/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(U) where U is the number of unique numbers in `A`
class Solution {
int atMost(vector<int> &A, int k) {
int distinct = 0, i = 0, j = 0, N = A.size(), ans = 0;
unordered_map<int, int> cnt;
for (; j < N; ++j) {
distinct += ++cnt[A[j]] == 1;
while (distinct > k) distinct -= --cnt[A[i++]] == 0;
ans += j - i;
}
return ans;
}
public:
int subarraysWithKDistinct(vector<int>& A, int k) {
return atMost(A, k) - atMost(A, k - 1);
}
};