# Count Substrings That Satisfy K-Constraint I
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-substrings-that-satisfy-k-constraint-i)
Canonical: https://scaleengineer.com/dsa/problems/count-substrings-that-satisfy-k-constraint-i
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** String
---
## 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**.

**Example 1:**

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

**Output:** 12

**Explanation:**

Every substring of `s` except the substrings `"1010"`, `"10101"`, and `"0101"` satisfies the k-constraint.

**Example 2:**

**Input:** s = "1010101", k = 2

**Output:** 25

**Explanation:**

Every substring of `s` except the substrings with a length greater than 5 satisfies the k-constraint.

**Example 3:**

**Input:** s = "11111", k = 1

**Output:** 15

**Explanation:**

All substrings of `s` satisfy the k-constraint.

**Constraints:**

* `1 <= s.length <= 50 `
* `1 <= k <= s.length`
* `s[i]` is either `'0'` or `'1'`.

# Approaches
## Brute Force Enumeration
This is the most straightforward and naive approach. The idea is to systematically generate every possible substring of the input string `s`. For each generated substring, we then perform a check to see if it satisfies the k-constraint. This check involves counting the number of '0's and '1's within that specific substring and comparing them against `k`.
**Time:** O(N^3). There are O(N^2) substrings. For each substring, which has an average length of O(N), we iterate through it to count characters. This results in a total time complexity of O(N^2 * N) = O(N^3). · **Space:** O(N). In each iteration, a new substring of length up to N can be created, requiring O(N) space. The exact space usage depends on the Java implementation of `substring`.
**Pros:** Very simple to understand and implement.; Correctly solves the problem.
**Cons:** Highly inefficient due to its cubic time complexity.; For each of the O(N^2) substrings, it re-scans the substring, leading to redundant work.; Will be too slow for larger values of N, although it passes for the given constraints.
### Explanation
The implementation involves two nested loops to define the start and end points of all substrings. The outer loop, with index `i`, determines the starting character of the substring. The inner loop, with index `j`, determines the ending character. This generates all `N * (N + 1) / 2` substrings. For each substring, a third loop (or a similar character-by-character scan) is used to 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 total counter. This method is easy to conceptualize but performs a lot of repetitive work.

```java
class Solution {
    public int countKConstraintSubstrings(String s, int k) {
        int n = s.length();
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Extract the substring
                String sub = s.substring(i, j + 1);
                int zeros = 0;
                int ones = 0;
                // Count 0s and 1s in the substring
                for (char c : sub.toCharArray()) {
                    if (c == '0') {
                        zeros++;
                    } else {
                        ones++;
                    }
                }
                // Check the k-constraint
                if (zeros <= k || ones <= k) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   Initialize a counter `validSubstrings` to 0.
*   Use a nested loop to generate all substrings. The outer loop `i` runs from `0` to `n-1` (start index), and the inner loop `j` runs from `i` to `n-1` (end index).
*   For each pair `(i, j)`, extract the substring `sub = s.substring(i, j + 1)`.
*   Count the number of '0's (`zeros`) and '1's (`ones`) in `sub` by iterating through it.
*   If `zeros <= k` or `ones <= k`, increment `validSubstrings`.
*   After checking all substrings, return `validSubstrings`.

## Optimized Iteration with Running Counts
We can significantly improve upon the brute-force approach by eliminating the redundant counting. Instead of generating a new substring and counting its characters from scratch every time, we can iterate through all possible start points and extend the substring one character at a time, maintaining a running count of '0's and '1's.
**Time:** O(N^2). The two nested loops iterate through all O(N^2) substrings, and the work inside the inner loop is now O(1). · **Space:** O(1). We only use a few extra variables to store the running counts and pointers, regardless of the input size.
**Pros:** A significant improvement in time complexity over the O(N^3) approach.; Simple to implement and easy to understand.; Efficient enough for the given constraints and many other problems.
**Cons:** While much better than the brute-force approach, it is not the most optimal solution.; For very large N, an O(N^2) solution would be too slow.
### Explanation
This approach still uses two nested loops to consider all substrings. The outer loop fixes the start index `i`. The inner loop iterates from `i` to the end of the string with index `j`, effectively extending the substring `s[i...j]` by one character in each step. We maintain two variables, `zeros` and `ones`, to store the counts for the current substring `s[i...j]`. When `j` increments, we just look at the new character `s.charAt(j)` and update the counts. This check-and-update step is O(1). Since we do this for every substring, the total time complexity is reduced to O(N^2).

```java
class Solution {
    public int countKConstraintSubstrings(String s, int k) {
        int n = s.length();
        int count = 0;
        for (int i = 0; i < n; i++) {
            int zeros = 0;
            int ones = 0;
            for (int j = i; j < n; j++) {
                // Update running counts for the substring s[i..j]
                if (s.charAt(j) == '0') {
                    zeros++;
                } else {
                    ones++;
                }
                // Check the k-constraint
                if (zeros <= k || ones <= k) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   Initialize a counter `validSubstrings` to 0.
*   Use an outer loop `i` from `0` to `n-1` to fix the starting point of the substrings.
*   Inside the outer loop, initialize `zeros = 0` and `ones = 0`.
*   Use an inner loop `j` from `i` to `n-1` to extend the substring to the right, one character at a time.
*   For each character `s.charAt(j)`, update the `zeros` and `ones` counts in O(1) time.
*   After each update, check if `zeros <= k` or `ones <= k`. If true, it means the current substring `s.substring(i, j + 1)` is valid, so increment `validSubstrings`.
*   Return `validSubstrings` after the loops complete.

## Sliding Window with Inclusion-Exclusion
The most efficient approach solves the problem in linear time using a combination of the Principle of Inclusion-Exclusion and the sliding window technique. The problem asks for the count of substrings satisfying condition A OR condition B. This can be calculated as `count(A) + count(B) - count(A AND B)`. Each of these three counts can be calculated efficiently using a sliding window.
**Time:** O(N). Each of the three helper functions uses a sliding window where the `left` and `right` pointers each traverse the string only once. This results in O(N) time for each, and thus O(N) overall. · **Space:** O(1). We only use a constant number of variables for counts and pointers.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Uses a common and powerful pattern (sliding window) that is applicable to many other problems.
**Cons:** The logic is more complex as it involves the inclusion-exclusion principle.; Requires implementing three separate (though similar) traversals of the string.
### Explanation
A sliding window is a powerful technique for problems involving contiguous subarrays or substrings. We can write a generic helper function `countWithAtMost(...)` that takes a condition and counts the number of substrings satisfying it.

1.  **`count(zeros <= k)`**: We use a sliding window `[left, right]`. We expand the window by moving `right`. We keep a count of zeros in the window. If `zeros > k`, we shrink the window from the left by moving `left` forward until the condition `zeros <= k` is met again. For each position of `right`, the number of valid substrings ending at `right` is `right - left + 1`. We sum this up for all `right`.
2.  **`count(ones <= k)`**: This is calculated similarly, but we track the count of ones.
3.  **`count(zeros <= k AND ones <= k)`**: Again, we use a sliding window. This time, the window is invalid if `zeros > k` OR `ones > k`. We shrink the window from the left until both conditions are satisfied.

Finally, we combine the results using the inclusion-exclusion formula to get the answer.

```java
class Solution {
    public int countKConstraintSubstrings(String s, int k) {
        // |A U B| = |A| + |B| - |A intersect B|
        // A = substrings with at most k zeros
        // B = substrings with at most k ones
        long countA = countWithAtMost(s, k, '0');
        long countB = countWithAtMost(s, k, '1');
        long countA_and_B = countWithAtMostBoth(s, k);
        
        return (int)(countA + countB - countA_and_B);
    }

    // Counts substrings with at most k occurrences of `targetChar`
    private long countWithAtMost(String s, int k, char targetChar) {
        int n = s.length();
        long count = 0;
        int left = 0;
        int charCount = 0;
        for (int right = 0; right < n; right++) {
            if (s.charAt(right) == targetChar) {
                charCount++;
            }
            while (charCount > k) {
                if (s.charAt(left) == targetChar) {
                    charCount--;
                }
                left++;
            }
            count += (right - left + 1);
        }
        return count;
    }

    // Counts substrings with at most k zeros AND at most k ones
    private long countWithAtMostBoth(String s, int k) {
        int n = s.length();
        long count = 0;
        int left = 0;
        int zeros = 0;
        int ones = 0;
        for (int right = 0; right < n; right++) {
            if (s.charAt(right) == '0') {
                zeros++;
            } else {
                ones++;
            }
            while (zeros > k || ones > k) {
                if (s.charAt(left) == '0') {
                    zeros--;
                } else {
                    ones--;
                }
                left++;
            }
            count += (right - left + 1);
        }
        return count;
    }
}
```
### Algorithm
*   The problem asks for the number of substrings where `(count('0') <= k) OR (count('1') <= k)`.
*   Use the Principle of Inclusion-Exclusion: `|A U B| = |A| + |B| - |A ∩ B|`.
    *   Let `A` be the set of substrings with at most `k` zeros.
    *   Let `B` be the set of substrings with at most `k` ones.
    *   Let `A ∩ B` be the set of substrings with at most `k` zeros AND at most `k` ones.
*   Create a helper function, e.g., `countAtMost(k, condition)`, that uses a sliding window to count substrings satisfying a given condition in O(N) time.
*   The sliding window `[left, right]` expands by incrementing `right`. If the condition is violated, it shrinks by incrementing `left`.
*   At each step `right`, the number of valid substrings ending at `right` is `right - left + 1`.
*   Calculate the final result by calling the helper function for each of the three cases: `count(A) + count(B) - count(A ∩ B)`.

# Solutions
### Java

```java
class Solution {
public
  int countKConstraintSubstrings(String s, int k) {
    int cnt0 = 0, cnt1 = 0;
    int ans = 0, l = 0;
    for (int r = 0; r < s.length(); ++r) {
      int x = s.charAt(r) - '0';
      cnt0 += x ^ 1;
      cnt1 += x;
      while (cnt0 > k && cnt1 > k) {
        int y = s.charAt(l++) - '0';
        cnt0 -= y ^ 1;
        cnt1 -= y;
      }
      ans += r - l + 1;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countKConstraintSubstrings(string s, int k) {
    int cnt0 = 0, cnt1 = 0;
    int ans = 0, l = 0;
    for (int r = 0; r < s.length(); ++r) {
      int x = s[r] - '0';
      cnt0 += x ^ 1;
      cnt1 += x;
      while (cnt0 > k && cnt1 > k) {
        int y = s[l++] - '0';
        cnt0 -= y ^ 1;
        cnt1 -= y;
      }
      ans += r - l + 1;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int: cnt0 = cnt1 = 0 ans = l = 0 for r, c in enumerate(s): cnt0 += int(c) ^ 1 cnt1 += int(c) while cnt0 > k and cnt1 > k: cnt0 -= int(s[l]) ^ 1 cnt1 -= int(s[l]) l += 1 ans += r - l + 1 return ans

```