Scale Engineer

Count Substrings That Satisfy K-Constraint II

Hard
#2895Time: O(Q * N^2), where Q is the number of queries and N is the length of the string. For each query, the two nested loops run in O(L^2) where L is the length of the query range (r-l+1), which can be up to N.Space: O(1) extra space, excluding the space for the output array.
Patterns
Sliding WindowPrefix Sum
Algorithms
Binary Search
Data structures
ArrayString

Prompt

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:

  • The number of 0's in the string is at most k.
  • The number of 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 <= 105
  • s[i] is either '0' or '1'.
  • 1 <= k <= s.length
  • 1 <= queries.length <= 105
  • queries[i] == [li, ri]
  • 0 <= li <= ri < s.length
  • All queries are distinct.

Approaches

3 approaches with complexity analysis and trade-offs.

This is the most straightforward approach. For each query, we iterate through all possible substrings within the given range [l, r]. For each of these substrings, we count the number of '0's and '1's to check if it satisfies the k-constraint. To make this slightly more efficient than re-counting for every substring, we can maintain running counts of zeros and ones as we extend the substring from a fixed starting point.

Algorithm

  • For each query [l, r] in queries:
    • Initialize valid_count = 0.
    • Iterate through all possible start indices i from l to r.
      • Initialize zeros = 0, ones = 0.
      • Iterate through all possible end indices j from i to r.
        • Update zeros and ones based on s[j].
        • If zeros <= k or ones <= k, increment valid_count.
    • Add valid_count to the answer list.

Walkthrough

The brute-force method directly translates the problem statement into code. We are given Q queries. For each query [l, r], we need to examine every substring of s[l..r]. A substring is defined by its start and end indices. We can use nested loops to generate all such pairs of indices (i, j) where l <= i <= j <= r.

For each substring s[i..j], we then count the occurrences of '0's and '1's. If the count of '0's is at most k, or the count of '1's is at most k, we increment a counter for the current query. After checking all substrings for the query [l, r], the value of the counter is our answer for that query.

An optimization is to fix the starting point i and extend the endpoint j. As j increments, we can update the counts of '0's and '1's in O(1) time instead of recounting the entire substring s[i..j], which would take O(j-i+1) time. This improves the complexity for a single query from O(L^3) to O(L^2), where L is the length of the query range.

class Solution {    public long[] countSubstrings(String s, int k, int[][] queries) {        int q = queries.length;        long[] ans = new long[q];        for (int i = 0; i < q; i++) {            int l = queries[i][0];            int r = queries[i][1];            long count = 0;            for (int start = l; start <= r; start++) {                int zeros = 0;                int ones = 0;                for (int end = start; end <= r; end++) {                    if (s.charAt(end) == '0') {                        zeros++;                    } else {                        ones++;                    }                    if (zeros <= k || ones <= k) {                        count++;                    }                }            }            ans[i] = count;        }        return ans;    }}

Complexity

Time

O(Q * N^2), where Q is the number of queries and N is the length of the string. For each query, the two nested loops run in O(L^2) where L is the length of the query range (r-l+1), which can be up to N.

Space

O(1) extra space, excluding the space for the output array.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires minimal space.

Cons

  • Extremely inefficient and will result in a 'Time Limit Exceeded' error for the given constraints.

Solutions

class Solution {public  long[] countKConstraintSubstrings(String s, int k, int[][] queries) {    int[] cnt = new int[2];    int n = s.length();    int[] d = new int[n];    Arrays.fill(d, n);    long[] pre = new long[n + 1];    for (int i = 0, j = 0; j < n; ++j) {      cnt[s.charAt(j) - '0']++;      while (cnt[0] > k && cnt[1] > k) {        d[i] = j;        cnt[s.charAt(i++) - '0']--;      }      pre[j + 1] = pre[j] + j - i + 1;    }    int m = queries.length;    long[] ans = new long[m];    for (int i = 0; i < m; ++i) {      int l = queries[i][0], r = queries[i][1];      int p = Math.min(r + 1, d[l]);      long a = (1L + p - l) * (p - l) / 2;      long b = pre[r + 1] - pre[p];      ans[i] = a + b;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem