Tap here to switch tabs
Problem
Submissions

Problem: Count Substrings That Satisfy K-Constraint II

Count Substrings That Satisfy K-Constraint II asks you to use a binary string and count, for each query range, substrings with at most k zeros or at most k ones, returning all counts.

Statement

You are given a binary string s and an integer k. You are also given a 2D2 {D} integer array queries, where each queries[i] = [l_i, r_i].

A binary string satisfies the kk constraint if at least one of the following conditions holds:

  • The number of occurrences of 00 is at most k.

  • The number of occurrences of 11 is at most k.

Return an integer array ans of length queries.length, where ans[i] represents the total number of substrings of s within the range from index l_i to index r_i that satisfy the kk constraint.

Constraints:

  • 1≤1 \leq s.length ≤105\leq 10^5

  • s[i] is either 00 or 11.

  • 1≤1 \leq k ≤\leq s.length

  • 1≤1 \leq queries.length ≤105\leq 10^5

  • queries[i] == [l_i, r_i]

  • 0≤0 \leq l_i ≤\leq r_i << s.length

  • All queries are distinct.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Count Substrings That Satisfy K-Constraint II

Count Substrings That Satisfy K-Constraint II asks you to use a binary string and count, for each query range, substrings with at most k zeros or at most k ones, returning all counts.

Statement

You are given a binary string s and an integer k. You are also given a 2D2 {D} integer array queries, where each queries[i] = [l_i, r_i].

A binary string satisfies the kk constraint if at least one of the following conditions holds:

  • The number of occurrences of 00 is at most k.

  • The number of occurrences of 11 is at most k.

Return an integer array ans of length queries.length, where ans[i] represents the total number of substrings of s within the range from index l_i to index r_i that satisfy the kk constraint.

Constraints:

  • 1≤1 \leq s.length ≤105\leq 10^5

  • s[i] is either 00 or 11.

  • 1≤1 \leq k ≤\leq s.length

  • 1≤1 \leq queries.length ≤105\leq 10^5

  • queries[i] == [l_i, r_i]

  • 0≤0 \leq l_i ≤\leq r_i << s.length

  • All queries are distinct.