Count Substrings That Satisfy K-Constraint I

Count Substrings That Satisfy K-Constraint I

What is this problem about?

The Count Substrings That Satisfy K-Constraint I coding problem asks you to look at a binary string (consisting of '0's and '1's) and an integer $k$. A substring is said to satisfy the "$k$-constraint" if either the count of '0's in it is at most $k$, OR the count of '1's in it is at most $k$.

You need to find the total number of substrings that satisfy this condition.

Why is this asked in interviews?

This problem is a classic sliding window interview pattern question asked by Microsoft and Google. It tests the ability to translate a logical "OR" condition into a window-management strategy. It also checks if you can identify that once a window satisfies a condition, any further reduction of that window (making it smaller) will also satisfy the condition. This "monotonic" property is key to an efficient solution.

Algorithmic pattern used

The Sliding Window pattern is the most efficient choice here.

1. Maintain two pointers, left and right.
2. Expand the right pointer and update the counts of '0's and '1's.
3. If both counts exceed $k$ (violating the "either/or" rule), shrink the window from the left until the constraint is restored.
4. For every right position, the number of valid substrings ending at right is right - left + 1.
5. Sum these values to get the total.

Example explanation

s = "10101", k = 1

1. right = 0: "1". 0 zeros, 1 one. Valid. Count += 1.
2. right = 1: "10". 1 zero, 1 one. Valid. Count += 2 (substrings "0", "10").
3. right = 2: "101". 1 zero, 2 ones. Valid ($1 \le k$). Count += 3 ("1", "01", "101").
4. right = 3: "1010". 2 zeros, 2 ones. Invalid (both $> k$).
5. Shrink left to 1: "010". Invalid.
6. Shrink left to 2: "10". Valid ($1 \le k$). Count += 2 ("0", "10"). ... continue.

Common mistakes candidates make

• Misinterpreting the OR: Thinking the substring must have both '0's and '1's $\le k$.
• Inefficient counting: Trying to generate all $O(N^2)$ substrings and checking each.
• Pointer logic: Not correctly updating the running counts when the left pointer moves.

Interview preparation tip

Whenever a problem asks to "Count all substrings satisfying a condition," check if the condition is "stable." If a substring is valid, does making it smaller (shrinking from either side) keep it valid? If yes, sliding window is your go-to tool.