Count Substrings That Satisfy K-Constraint I
EasyPrompt
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'.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a counter
validSubstringsto 0. - Use a nested loop to generate all substrings. The outer loop
iruns from0ton-1(start index), and the inner loopjruns fromiton-1(end index). - For each pair
(i, j), extract the substringsub = s.substring(i, j + 1). - Count the number of '0's (
zeros) and '1's (ones) insubby iterating through it. - If
zeros <= korones <= k, incrementvalidSubstrings. - After checking all substrings, return
validSubstrings.
Walkthrough
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.
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; }}Complexity
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`.
Trade-offs
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.
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.
Algorithm
- Initialize a counter
validSubstringsto 0. - Use an outer loop
ifrom0ton-1to fix the starting point of the substrings. - Inside the outer loop, initialize
zeros = 0andones = 0. - Use an inner loop
jfromiton-1to extend the substring to the right, one character at a time. - For each character
s.charAt(j), update thezerosandonescounts in O(1) time. - After each update, check if
zeros <= korones <= k. If true, it means the current substrings.substring(i, j + 1)is valid, so incrementvalidSubstrings. - Return
validSubstringsafter the loops complete.
Walkthrough
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).
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; }}Complexity
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.
Trade-offs
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.
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.
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
Abe the set of substrings with at mostkzeros. - Let
Bbe the set of substrings with at mostkones. - Let
A ∩ Bbe the set of substrings with at mostkzeros AND at mostkones.
- Let
- 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 incrementingright. If the condition is violated, it shrinks by incrementingleft. - At each step
right, the number of valid substrings ending atrightisright - left + 1. - Calculate the final result by calling the helper function for each of the three cases:
count(A) + count(B) - count(A ∩ B).
Walkthrough
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.
count(zeros <= k): We use a sliding window[left, right]. We expand the window by movingright. We keep a count of zeros in the window. Ifzeros > k, we shrink the window from the left by movingleftforward until the conditionzeros <= kis met again. For each position ofright, the number of valid substrings ending atrightisright - left + 1. We sum this up for allright.count(ones <= k): This is calculated similarly, but we track the count of ones.count(zeros <= k AND ones <= k): Again, we use a sliding window. This time, the window is invalid ifzeros > kORones > 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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.