Watch 10 video solutions for Count Substrings That Satisfy K-Constraint II, a hard level problem involving Array, String, Binary Search. This walkthrough by codestorywithMIK has 6,249 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a binary string s and an integer k.
You are also given a 2D integer array queries, where queries[i] = [li, ri].
A binary string satisfies the k-constraint if either of the following conditions holds:
0's in the string is at most k.1's in the string is at most k.Return an integer array answer, where answer[i] is the number of substrings of s[li..ri] that satisfy the k-constraint.
Example 1:
Input: s = "0001111", k = 2, queries = [[0,6]]
Output: [26]
Explanation:
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".
Example 2:
Input: s = "010101", k = 1, queries = [[0,5],[1,4],[2,3]]
Output: [15,9,3]
Explanation:
The substrings of s with a length greater than 3 do not satisfy the k-constraint.
Constraints:
1 <= s.length <= 105s[i] is either '0' or '1'.1 <= k <= s.length1 <= queries.length <= 105queries[i] == [li, ri]0 <= li <= ri < s.length