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
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 substrings of s that satisfy the k-constraint.
Example Inputs
- 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'.
Brute Force Approach
a.Approach
- Use a nested loop to iterate through all possible substrings of the binary string
s.
- For each substring, count the number of
0s and 1s.
- If either the count of
0s or 1s is less than or equal to k, consider it as satisfying the constraint.
b.Steps
- Start with an empty count for substrings satisfying the k-constraint.
- For each substring, check the number of
0s and 1s.
- If either count is at most
k, increment the count.
c.Time and Space Complexity
- Time Complexity:
O(n^3), where n is the length of s, due to the substring generation and counting steps.
- Space Complexity:
O(1) for auxiliary space, as we only use a few counters.
d.Code Snippet
e.Dry Run
Input: s = "10101", k = 1
- All substrings are checked.
- Substrings "1010", "10101", and "0101" are identified as not satisfying the k-constraint.
Efficient Approach
a.Approach (Sliding Window)
- Use two pointers to create a sliding window for substrings.
- For each window, maintain a count of
0s and 1s.
- Expand or contract the window to maintain the counts such that either
0s or 1s stay below or equal to k.
b.Steps
- Initialize left and right pointers.
- Expand the window by moving the right pointer and updating
0 and 1 counts.
- If either count exceeds
k, slide the left pointer to reduce the window size and adjust the counts.
- Count substrings within the valid window sizes.
c.Time and Space Complexity
- Time Complexity:
O(n), where n is the length of s, due to the single-pass sliding window.
- Space Complexity:
O(1) for auxiliary space, as only counters are used.
d.Code Snippet
e.Dry Run
Input: s = "10101", k = 1
- Using sliding window, move the pointers and update counts to keep valid substrings.
- Count all valid windows.
Complexity Analysis
Brute Force
- Time Complexity:
O(n^3)
- Space Complexity:
O(1)
Optimized
- Time Complexity:
O(n)
- Space Complexity:
O(1)
Conclusion
This guide illustrates the significant difference between brute force and efficient solutions. The sliding window approach optimizes the solution by reducing the time complexity from O(n^3) to O(n), making it feasible for larger inputs within the given constraints.