Problem Description

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 0s in the string is at most k.
• The number of 1s in the string is at most k.

Return an integer denoting the number of non-empty substrings of s that satisfy the k-constraint.

Intuition

The solution uses a sliding window approach. The idea is to maintain a window containing a current substring of s and keep track of how many 0s and 1s are present within this window.

The approach is as follows:

1. Initialize counters for 0s and 1s in the current window. Also, maintain pointers l and r representing the left and right boundary of the window.
2. Traverse the string character by character. For each character, update the count of 0s or 1s, depending on whether the character is a 0 or a 1.
3. If both 0 and 1 counts exceed k, keep increasing the left boundary (l) until at least one count is k or smaller. This ensures that the current window satisfies the k-constraint.
4. Each time the window is shifted, calculate the number of valid substrings from the current valid window, which is the number of positions r - l + 1.
5. Continue expanding the right boundary until the end of the string.

The algorithm efficiently counts valid substrings while iterating through the string with a time complexity of O(n), where n is the length of s.

Learn more about Sliding Window patterns.

Solution Approach

The solution employs the Sliding Window technique, which is well-suited for problems involving arrays or strings where we need to find a condition that holds for contiguous subarrays or substrings.

1. Initialization: We begin by initializing two variables cnt and ans. The cnt array stores the count of 0s and 1s in the current window. The variable ans will keep track of the total number of substrings that satisfy the k-constraint. Additionally, a variable l is initialized as 0, which marks the left boundary of our sliding window.

cnt = [0, 0]
ans = l = 0

2. Window Expansion: Iterate over each character in the binary string s using its index r. Convert the character to an integer (0 or 1) and increase its count in the cnt array.

for r, x in enumerate(map(int, s)):
    cnt[x] += 1

3. Valid Window Check: After updating the count, check if both counts (cnt[0] and cnt[1]) exceed k. If they do, it means the substring starting from l to r is invalid. Hence, increment the left boundary l until at least one count is k or less.

while cnt[0] > k and cnt[1] > k:
    cnt[int(s[l])] -= 1
    l += 1

4. Counting Valid Substrings: If the current window satisfies the k-constraint, all substrings starting with an index between l and r are valid. Thus, the total number of such substrings is r - l + 1. Add this count to ans.

ans += r - l + 1

5. Result: After the loop completes, ans will contain the total number of substrings that fulfill the k-constraint.

Finally, return ans as the result.

return ans

This approach efficiently finds all valid substrings with a time complexity of O(n), iterating through the string a minimal number of times due to the sliding window mechanism.

Example Walkthrough

Let's walk through an example to illustrate the solution approach.

Consider the binary string s = "11001" and the integer k = 2.

We'll apply the sliding window technique as follows:

1. Initialization:

   • cnt = [0, 0] to track the number of 0s and 1s in the window.
   • ans = 0 to accumulate the total number of valid substrings.
   • l = 0 to mark the left boundary of the window.

2. Window Expansion: Our goal is to iterate over every character in s and expand the window by including each character at the right end r:

   • At r = 0, x = 1: Update cnt to [0, 1].
   • At r = 1, x = 1: Update cnt to [0, 2]. The window is valid as the number of 0s or 1s is less than or equal to k.
   • Count the valid substrings from l = 0 to r = 1. ans = ans + (r - l + 1) = 0 + 2 = 2.

3. Continue Expanding:

   • At r = 2, x = 0: Update cnt to [1, 2]. Window [0,2] is still valid.
   • Count the valid substrings: ans = 2 + (r - l + 1) = 5.
   • At r = 3, x = 0: Update cnt to [2, 2]. This window [0,3] remains valid.
   • Count the valid substrings: ans = 5 + (r - l + 1) = 9.

4. Check Constraints:

   • At r = 4, x = 1: Update cnt to [2, 3]. Now, both counts exceed k. We need to increment l until our window is valid.
   • Increment l to 1: cnt becomes [2, 2], making the window [1,4] valid again.
   • Count the valid substrings: ans = 9 + (r - l + 1) = 13.

5. Final Result:

   • At the end of the iteration, ans = 13 which is the total number of substrings that satisfy the k-constraint.

In this example, we efficiently counted all qualifying substrings using a sliding window, ensuring time complexity of O(n).

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the string s. This is because the algorithm goes through each character of the string exactly once with two pointers l and r iterating over the string, achieving a linear time complexity.

The space complexity is O(1), as the algorithm uses a fixed amount of space regardless of the input size. The space usage includes a list cnt with two elements to count occurrences of 0 and 1, and a few integer variables for processing.

Learn more about how to find time and space complexity quickly.