3859. Count Subarrays With K Distinct Integers Hard

1/**
2 * [3859] Count Subarrays With K Distinct Integers
3 *
4 * You are given an integer array nums and two integers k and m.
5 * Return an integer denoting the count of <span data-keyword="subarray-nonempty">subarrays</span> of nums such that:
6 * 
7 * 	The subarray contains exactly k distinct integers.
8 * 	Within the subarray, each distinct integer appears at least m times.
9 * 
10 *  
11 * <strong class="example">Example 1:
12 * <div class="example-block">
13 * Input: <span class="example-io">nums = [1,2,1,2,2], k = 2, m = 2</span>
14 * Output: <span class="example-io">2</span>
15 * Explanation:
16 * The possible subarrays with k = 2 distinct integers, each appearing at least m = 2 times are:
17 * <table style="border: 1px solid black;">
18 * 	<thead>
19 * 		<tr>
20 * 			<th style="border: 1px solid black;">Subarray</th>
21 * 			<th style="border: 1px solid black;">Distinct<br />
22 * 			numbers</th>
23 * 			<th style="border: 1px solid black;">Frequency</th>
24 * 		</tr>
25 * 	</thead>
26 * 	<tbody>
27 * 		<tr>
28 * 			<td style="border: 1px solid black;">[1, 2, 1, 2]</td>
29 * 			<td style="border: 1px solid black;">{1, 2} &rarr; 2</td>
30 * 			<td style="border: 1px solid black;">{1: 2, 2: 2}</td>
31 * 		</tr>
32 * 		<tr>
33 * 			<td style="border: 1px solid black;">[1, 2, 1, 2, 2]</td>
34 * 			<td style="border: 1px solid black;">{1, 2} &rarr; 2</td>
35 * 			<td style="border: 1px solid black;">{1: 2, 2: 3}</td>
36 * 		</tr>
37 * 	</tbody>
38 * </table>
39 * Thus, the answer is 2.
40 * </div>
41 * <strong class="example">Example 2:
42 * <div class="example-block">
43 * Input: <span class="example-io">nums = [3,1,2,4], k = 2, m = 1</span>
44 * Output: <span class="example-io">3</span>
45 * Explanation:
46 * The possible subarrays with k = 2 distinct integers, each appearing at least m = 1 times are:
47 * <table style="border: 1px solid black;">
48 * 	<thead>
49 * 		<tr>
50 * 			<th style="border: 1px solid black;">Subarray</th>
51 * 			<th style="border: 1px solid black;">Distinct<br />
52 * 			numbers</th>
53 * 			<th style="border: 1px solid black;">Frequency</th>
54 * 		</tr>
55 * 	</thead>
56 * 	<tbody>
57 * 		<tr>
58 * 			<td style="border: 1px solid black;">[3, 1]</td>
59 * 			<td style="border: 1px solid black;">{3, 1} &rarr; 2</td>
60 * 			<td style="border: 1px solid black;">{3: 1, 1: 1}</td>
61 * 		</tr>
62 * 		<tr>
63 * 			<td style="border: 1px solid black;">[1, 2]</td>
64 * 			<td style="border: 1px solid black;">{1, 2} &rarr; 2</td>
65 * 			<td style="border: 1px solid black;">{1: 1, 2: 1}</td>
66 * 		</tr>
67 * 		<tr>
68 * 			<td style="border: 1px solid black;">[2, 4]</td>
69 * 			<td style="border: 1px solid black;">{2, 4} &rarr; 2</td>
70 * 			<td style="border: 1px solid black;">{2: 1, 4: 1}</td>
71 * 		</tr>
72 * 	</tbody>
73 * </table>
74 * Thus, the answer is 3.
75 * </div>
76 *  
77 * Constraints:
78 * 
79 * 	1 <= nums.length <= 10^5
80 * 	1 <= nums[i] <= 10^5
81 * 	1 <= k, m <= nums.length
82 * 
83 */
84pub struct Solution {}
85
86// problem: https://leetcode.com/problems/count-subarrays-with-k-distinct-integers/
87// discuss: https://leetcode.com/problems/count-subarrays-with-k-distinct-integers/discuss/?currentPage=1&orderBy=most_votes&query=
88
89// submission codes start here
90
91impl Solution {
92    pub fn count_subarrays(nums: Vec<i32>, k: i32, m: i32) -> i64 {
93        
94    }
95}
96
97// submission codes end
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102
103    #[test]
104    fn test_3859() {
105    }
106}
107