Count Substrings That Satisfy K-Constraint II

Count Substrings That Satisfy K-Constraint II - Problem

Array String Binary Search Sliding Window Prefix Sum Hard

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

For each query, you need to count how many substrings within the range s[li..ri] satisfy the k-constraint.

Goal: Return an integer array answer, where answer[i] is the number of substrings of s[li..ri] that satisfy the k-constraint.

Example: If s = "0001111" and k = 2, then substrings like "00", "11", "001" all satisfy the constraint because they have ≤2 zeros OR ≤2 ones.

Input & Output

example_1.py — Basic Example

$ Input: s = "0001111", k = 2, queries = [[0,6]]

› Output: [26]

💡 Note: All substrings of s satisfy the constraint since each has ≤2 zeros OR ≤2 ones. Total substrings = 7×8/2 = 28, but some violate the constraint. After checking: 26 valid substrings.

example_2.py — Multiple Queries

$ Input: s = "010101", k = 1, queries = [[0,5],[1,4],[2,3]]

› Output: [15,9,3]

💡 Note: Query [0,5]: Full string has many valid substrings. Query [1,4]: Substring "1010" analysis. Query [2,3]: Substring "01" has 3 valid substrings: "0", "1", "01".

example_3.py — Edge Case

$ Input: s = "11111", k = 1, queries = [[0,4]]

› Output: [15]

💡 Note: All substrings satisfy constraint (≤1 ones OR ≤1 zeros). Since all are 1s, each substring has ≤1 zeros, so all 15 possible substrings are valid.

Constraints

1 ≤ s.length ≤ 10⁵
s[i] is either '0' or '1'
1 ≤ k ≤ s.length
1 ≤ queries.length ≤ 10⁵
queries[i] = [l_i, r_i]
0 ≤ l_i ≤ r_i < s.length

Visualization

Tap to expand

Understanding the Visualization

Set Tolerance Level

Establish k as maximum acceptable defects of either type

Find Valid Segments

Use sliding window to efficiently find all valid chip segments

Precompute Boundaries

Record the furthest valid position for each starting point

Answer Inspections

When managers ask about specific sections, use precomputed data

Key Takeaway

🎯 Key Insight: By precomputing the furthest valid position for each starting point using sliding window, we can answer any range query in O(1) time using mathematical formulas, achieving optimal O(N + Q) complexity.

Asked in

G Google 35 a Amazon 28 f Meta 22 ⊞ Microsoft 18

The optimal solution uses sliding window technique to precompute valid boundaries for each position, then applies mathematical counting to answer queries efficiently. Key insight: for each starting position, find the furthest ending position that satisfies the k-constraint, then use this to count valid substrings in O(N + Q) time.

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window + Prefix Sum (Optimal)	O(N + Q)	O(N)	Use sliding window to precompute valid ranges, then prefix sums for queries
Brute Force (Nested Loops)	O(Q × N³)	O(1)	Check every possible substring in each query range

Sliding Window + Prefix Sum (Optimal) — Algorithm Steps

For each position i, find the rightmost position j where substring s[i:j] satisfies k-constraint
Use sliding window with two pointers to efficiently compute these boundaries
Calculate contribution of each position to total valid substrings
Build prefix sum array for range query answering
Answer each query using prefix sum difference in O(1) time

Visualization

Tap to expand

Step-by-Step Walkthrough

Sliding Window Phase

Use two pointers to find valid ranges efficiently

Record Boundaries

For each position, record the furthest valid ending position

Calculate Contributions

Count how many valid substrings start at each position

Answer Queries

Use precomputed data to answer queries quickly

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long* countKConstraintSubstrings(char* s, int k, int** queries, int queriesSize, int* queriesColSize) {
    int n = strlen(s);
    int* right = (int*)malloc(n * sizeof(int));
    int left = 0, count0 = 0, count1 = 0;
    
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') count0++;
        else count1++;
        
        while (count0 > k && count1 > k) {
            if (s[left] == '0') count0--;
            else count1--;
            left++;
        }
        
        for (int j = left; j <= i; j++) {
            right[j] = i;
        }
    }
    
    for (int i = left; i < n; i++) {
        right[i] = n - 1;
    }
    
    long long* result = (long long*)malloc(queriesSize * sizeof(long long));
    for (int q = 0; q < queriesSize; q++) {
        int l = queries[q][0], r = queries[q][1];
        long long total = 0;
        
        for (int i = l; i <= r; i++) {
            int validEnd = (right[i] < r) ? right[i] : r;
            if (validEnd >= i) {
                total += validEnd - i + 1;
            }
        }
        result[q] = total;
    }
    
    free(right);
    return result;
}

Time & Space Complexity

Time Complexity

⏱️

O(N + Q)

O(N) preprocessing with sliding window + O(1) per query

✓ Linear Growth

Space Complexity

O(N)

Storing boundary arrays and prefix sums

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window + Prefix Sum (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler