Build confidence with an intuition-first walkthrough focused on sliding window fundamentals.
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:
0's in the string is at most k.1's in the string is at most k.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 <= 50 1 <= k <= s.lengths[i] is either '0' or '1'.Problem summary: 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 most k. The number of 1's in the string is at most k. Return an integer denoting the number of substrings of s that satisfy the k-constraint.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Sliding Window
"10101" 1
"1010101" 2
"11111" 1
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3258: Count Substrings That Satisfy K-Constraint I
class Solution {
public int countKConstraintSubstrings(String s, int k) {
int[] cnt = new int[2];
int ans = 0, l = 0;
for (int r = 0; r < s.length(); ++r) {
++cnt[s.charAt(r) - '0'];
while (cnt[0] > k && cnt[1] > k) {
cnt[s.charAt(l++) - '0']--;
}
ans += r - l + 1;
}
return ans;
}
}
// Accepted solution for LeetCode #3258: Count Substrings That Satisfy K-Constraint I
func countKConstraintSubstrings(s string, k int) (ans int) {
cnt := [2]int{}
l := 0
for r, c := range s {
cnt[c-'0']++
for ; cnt[0] > k && cnt[1] > k; l++ {
cnt[s[l]-'0']--
}
ans += r - l + 1
}
return
}
# Accepted solution for LeetCode #3258: Count Substrings That Satisfy K-Constraint I
class Solution:
def countKConstraintSubstrings(self, s: str, k: int) -> int:
cnt = [0, 0]
ans = l = 0
for r, x in enumerate(map(int, s)):
cnt[x] += 1
while cnt[0] > k and cnt[1] > k:
cnt[int(s[l])] -= 1
l += 1
ans += r - l + 1
return ans
// Accepted solution for LeetCode #3258: Count Substrings That Satisfy K-Constraint I
impl Solution {
pub fn count_k_constraint_substrings(s: String, k: i32) -> i32 {
let mut cnt = [0; 2];
let mut l = 0;
let mut ans = 0;
let s = s.as_bytes();
for (r, &c) in s.iter().enumerate() {
cnt[(c - b'0') as usize] += 1;
while cnt[0] > k && cnt[1] > k {
cnt[(s[l] - b'0') as usize] -= 1;
l += 1;
}
ans += r - l + 1;
}
ans as i32
}
}
// Accepted solution for LeetCode #3258: Count Substrings That Satisfy K-Constraint I
function countKConstraintSubstrings(s: string, k: number): number {
const cnt: [number, number] = [0, 0];
let [ans, l] = [0, 0];
for (let r = 0; r < s.length; ++r) {
cnt[+s[r]]++;
while (cnt[0] > k && cnt[1] > k) {
cnt[+s[l++]]--;
}
ans += r - l + 1;
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
For each starting index, scan the next k elements to compute the window aggregate. There are n−k+1 starting positions, each requiring O(k) work, giving O(n × k) total. No extra space since we recompute from scratch each time.
The window expands and contracts as we scan left to right. Each element enters the window at most once and leaves at most once, giving 2n total operations = O(n). Space depends on what we track inside the window (a hash map of at most k distinct elements, or O(1) for a fixed-size window).
Review these before coding to avoid predictable interview regressions.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.