Count Substrings That Satisfy K-Constraint I - Solution & Explanation
Problem Statement
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 mostk. - The number of
1's in the string is at mostk.
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 <= 501 <= k <= s.lengths[i]is either'0'or'1'.
Approach Overview
Problem Overview: You are given a binary string s and an integer k. A substring satisfies the k-constraint if the number of 0s in the substring is at most k or the number of 1s is at most k. The task is to count all substrings that satisfy this rule.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Generate every possible substring and count how many 0s and 1s it contains. Use two nested loops: the outer loop selects the starting index and the inner loop expands the substring one character at a time. Maintain running counts of zeros and ones while expanding the window so you don't recompute counts repeatedly. For each extension, check the condition zeros ≤ k or ones ≤ k; if true, increment the answer. This approach directly simulates the definition of the problem. The time complexity is O(n²) because every substring is examined, while space usage remains O(1). It works well for small strings and helps confirm correctness before optimizing.
Approach 2: Sliding Window / Two Pointers (O(n) time, O(1) space)
A substring becomes invalid only when both counts exceed k. That observation allows a sliding window solution. Maintain two pointers left and right representing the current window, along with counters for zeros and ones. Expand the window by moving right across the string and updating the appropriate counter. If both counters become greater than k, shrink the window by moving left forward and decreasing counts until at least one of them is ≤ k again.
For each position of right, every substring ending at right and starting between left and right is valid. That means you can add right - left + 1 to the answer. Each character enters and leaves the window at most once, giving a linear O(n) time complexity with constant O(1) extra space. This technique is a classic application of the two pointers pattern for substring counting problems on strings.
Recommended for interviews: Interviewers expect the sliding window solution. Starting with brute force shows you understand the problem definition and substring generation. Transitioning to the sliding window demonstrates the key insight: the window is invalid only when both character counts exceed k. Recognizing that property and converting it into a linear two‑pointer scan is the main skill being tested.
Approach 1: Brute Force Approach
In this approach, we check all possible substrings of the given binary string s. For each substring, we count the number of 0's and 1's, then check if the substring satisfies the k-constraint. This method is straightforward but may be inefficient for longer strings.
This solution iterates through each possible starting index of a substring, then extends the substring as long as it satisfies the k-constraint. If either the number of 0's or 1's exceeds k, we stop extending the substring from that starting index.
Complexity
The time complexity of this brute force approach is O(n2), where n is the length of the string. The space complexity is O(1) as we only use a few extra variables.
Approach 2: Sliding Window Approach
This approach utilizes a sliding window technique to optimize counting of valid substrings. We maintain two sliding windows – one for tracking substrings with zeros ≤ k and one for substrings with ones ≤ k. The aim is to adjust the window such that it remains valid and count all substrings possible within each window.
This solution employs a function helper to count valid substrings where either '0' or '1' is ≤ k. It uses a sliding window to adjust the window size dynamically and count all possible substrings within that valid window.
Complexity
The time complexity is O(n) for processing each character, and the space complexity is O(1) due to no additional data structures used.
Approach 3: Sliding Window
We use two variables cnt0 and cnt1 to record the number of 0s and 1s in the current window, respectively. We use ans to record the number of substrings that satisfy the k constraint, and l to record the left boundary of the window.
When we move the window to the right, if the number of 0s and 1s in the window both exceed k, we need to move the window to the left until the number of 0s and 1s in the window are both no greater than k. At this point, all substrings in the window satisfy the k constraint, and the number of such substrings is r - l + 1, where r is the right boundary of the window. We add this count to ans.
Finally, we return ans.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | The time complexity of this brute force approach is O(n2), where n is the length of the string. The space complexity is O(1) as we only use a few extra variables. |
| Sliding Window Approach | The time complexity is O(n) for processing each character, and the space complexity is O(1) due to no additional data structures used. |
| Sliding Window | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Useful for understanding the problem and validating logic on small inputs |
| Sliding Window / Two Pointers | O(n) | O(1) | Optimal approach for large strings; counts valid substrings in a single pass |
Video Solution
Count Substrings That Satisfy K-Constraint I & II | Detailed Explanation | Leetcode 3258 & 3261 • codestorywithMIK • 8,626 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Substrings That Satisfy K-Constraint I easy or hard?
Count Substrings That Satisfy K-Constraint I Python/Java solution
How to solve Count Substrings That Satisfy K-Constraint I in O(n)?
What is the best approach for Count Substrings That Satisfy K-Constraint I?
Is Count Substrings That Satisfy K-Constraint I asked at Google/Amazon/Meta?
What data structure is used in Count Substrings That Satisfy K-Constraint I?
What is the time complexity of Count Substrings That Satisfy K-Constraint I?
Ready to solve this problem?
Practice Count Substrings That Satisfy K-Constraint I with our built-in code editor and test cases.
Practice on FleetCode