3261. Count Substrings That Satisfy K-Constraint II Hard

1/**
2 * [3261] Count Substrings That Satisfy K-Constraint II
3 *
4 * You are given a binary string s and an integer k.
5 * You are also given a 2D integer array queries, where queries[i] = [li, ri].
6 * A binary string satisfies the k-constraint if either of the following conditions holds:
7 * 
8 * 	The number of 0's in the string is at most k.
9 * 	The number of 1's in the string is at most k.
10 * 
11 * Return an integer array answer, where answer[i] is the number of <span data-keyword="substring-nonempty">substrings</span> of s[li..ri] that satisfy the k-constraint.
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">s = "0001111", k = 2, queries = [[0,6]]</span>
16 * Output: <span class="example-io">[26]</span>
17 * Explanation:
18 * For the query [0, 6], all substrings of s[0..6] = "0001111" satisfy the k-constraint except for the substrings s[0..5] = "000111" and s[0..6] = "0001111".
19 * </div>
20 * <strong class="example">Example 2:
21 * <div class="example-block">
22 * Input: <span class="example-io">s = "010101", k = 1, queries = [[0,5],[1,4],[2,3]]</span>
23 * Output: <span class="example-io">[15,9,3]</span>
24 * Explanation:
25 * The substrings of s with a length greater than 3 do not satisfy the k-constraint.
26 * </div>
27 *  
28 * Constraints:
29 * 
30 * 	1 <= s.length <= 10^5
31 * 	s[i] is either '0' or '1'.
32 * 	1 <= k <= s.length
33 * 	1 <= queries.length <= 10^5
34 * 	queries[i] == [li, ri]
35 * 	0 <= li <= ri < s.length
36 * 	All queries are distinct.
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/count-substrings-that-satisfy-k-constraint-ii/
42// discuss: https://leetcode.com/problems/count-substrings-that-satisfy-k-constraint-ii/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46impl Solution {
47    pub fn count_k_constraint_substrings(s: String, k: i32, queries: Vec<Vec<i32>>) -> Vec<i64> {
48        
49    }
50}
51
52// submission codes end
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn test_3261() {
60    }
61}
62