Count substrings that satisfy k constraint i

String Sliding Window

78.9% acceptance

Feb 25, 2026

176

You are given a binary string s and an integer k. A binary string satisfies the k-constraint if the number of 0's or the number of 1's in it is at most k. Return the number of substrings of s that satisfy the k-constraint.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn count_k_constraint_substrings(s: String, k: i32) -> i32 {
    let k = k as usize;
    let b: Vec<usize> = s.bytes().map(|c| (c - b'0') as usize).collect();
    let n = b.len();
    let mut ans = 0i32;
    for l in 0..n {
      let (mut c0, mut c1) = (0usize, 0usize);
      for r in l..n {
        if b[r] == 0 { c0 += 1; } else { c1 += 1; }
        if c0 <= k || c1 <= k {
          ans += 1;
        }
      }
    }
    ans
  }
}