Count Substrings That Satisfy K-Constraint I

Count Substrings That Satisfy K-Constraint I - Problem

You are given a binary string s and an integer k.

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 denoting the number of substrings of s that satisfy the k-constraint.

Input & Output

Example 1 — Basic Case

$ Input: s = "10101", k = 1

› Output: 12

💡 Note: All substrings with length 1 satisfy the constraint (5 substrings). Substrings "10", "01", "10", "01" also satisfy it (4 more). Some length-3 substrings like "010" satisfy it too, totaling 12.

Example 2 — All Same Character

$ Input: s = "1111", k = 2

› Output: 10

💡 Note: All substrings satisfy the constraint since we have only 1s and the constraint allows up to 2 of any character. Total substrings = n(n+1)/2 = 4×5/2 = 10.

Example 3 — Small k

$ Input: s = "11001", k = 1

› Output: 9

💡 Note: Single characters always satisfy (5). "10", "00", "01" satisfy the constraint (3 more). "1100" has 2 ones and 2 zeros, violating the constraint for k=1. One more valid substring gives us 9.

Constraints

1 ≤ s.length ≤ 1000
s consists only of '0' and '1'
1 ≤ k ≤ s.length

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string s and constraint k

Process

Check each substring's 0s and 1s count

Output

Count of substrings where either count ≤ k

Key Takeaway

🎯 Key Insight: A substring is valid if it contains at most k zeros OR at most k ones

Asked in

M Microsoft 15 a Amazon 12

The key insight is that a substring satisfies the k-constraint if either the count of 0s ≤ k OR the count of 1s ≤ k. Best approach is sliding window with early termination to avoid unnecessary expansions. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Substrings	O(n³)	O(1)	Generate all possible substrings and check each one against the k-constraint
Sliding Window - Optimal Count	O(n²)	O(1)	Use sliding window technique to efficiently count valid substrings

Brute Force - Check All Substrings — Algorithm Steps

Step 1: For each starting position i from 0 to n-1
Step 2: For each ending position j from i to n-1, form substring s[i:j+1]
Step 3: Count 0s and 1s in current substring
Step 4: If count of 0s ≤ k OR count of 1s ≤ k, increment result

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

For each start position, create all substrings

Count Characters

Count 0s and 1s in each substring

Check Constraint

Valid if either count ≤ k

Code -

solution.c — C

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

int solution(char* s, int k) {
    int n = strlen(s);
    int count = 0;
    
    // Check all possible substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // Count 0s and 1s in substring s[i:j+1]
            int zeros = 0;
            int ones = 0;
            for (int idx = i; idx <= j; idx++) {
                if (s[idx] == '0') {
                    zeros++;
                } else {
                    ones++;
                }
            }
            
            // Check if substring satisfies k-constraint
            if (zeros <= k || ones <= k) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int k;
    scanf("%d", &k);
    
    int result = solution(s, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Two nested loops for start/end positions (O(n²)) × character counting for each substring (O(n))

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to count characters and track result

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

342 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

Brute Force - Check All Substrings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler