## Problem

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**.

**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.length`

`s[i]`

is either`'0'`

or`'1'`

.

## Solution

First attempt : Time complexity O(n3)

```
impl Solution {
pub fn count_k_constraint_substrings(s: String, k: i32) -> i32 {
let vec:Vec<char> = s.chars().collect();
let mut i: i32 = 0;
let mut output: i32 = 0;
let veclength: i32 = vec.len() as i32;
loop{
let subvec : Vec<char> = Vec::new();
let mut j:i32 = i+1;
loop{
if(j > veclength){
break;
}
//println!("");
let mut tempzero:i32 = k;
let mut tempone:i32 = k;
for pointer in i..j{
if(vec[pointer as usize] == '0' as char){
tempzero = tempzero -1;
}
if(vec[pointer as usize] == '1' as char){
tempone = tempone -1;
}
//println!("vec is : {:?}",vec[pointer as usize])
}
if(tempzero >= 0 as i32 || tempone >= 0 as i32){
output = output + 1;
}
j = j+1;
}
i = i+1;
if(i > veclength){
break;
}
}
// println!("{} {} {:?}",s,k, vec);
return(output);
}
}
```

Second attempt : Time complexity O(n3)

```
impl Solution {
pub fn count_k_constraint_substrings(s: String, k: i32) -> i32 {
let vec: Vec<char> = s.chars().collect();
let veclength = vec.len();
let mut prefix_zero = vec![0; veclength + 1];
let mut prefix_one = vec![0; veclength + 1];
for i in 0..veclength {
prefix_zero[i + 1] = prefix_zero[i] + if vec[i] == '0' { 1 } else { 0 };
prefix_one[i + 1] = prefix_one[i] + if vec[i] == '1' { 1 } else { 0 };
}
let mut output = 0;
for i in 0..veclength {
for j in i..veclength {
let count_zero = prefix_zero[j + 1] - prefix_zero[i];
let count_one = prefix_one[j + 1] - prefix_one[i];
if count_zero <= k as usize || count_one <= k as usize {
output += 1;
} else {
break;
}
}
}
output
}
}
```

A freelance web developer with a decade of experience in creating high-quality, scalable web solutions. His expertise spans PHP, WordPress, Node.js, MySQL, MongoDB, and e-commerce development, ensuring a versatile approach to each project. Aadi’s commitment to client satisfaction is evident in his track record of over 200 successful projects, marked by innovation, efficiency, and a customer-centric philosophy.

As a professional who values collaboration and open communication, Aadi has built a reputation for delivering projects that exceed expectations while adhering to time and budget constraints. His proactive and problem-solving mindset makes him an ideal partner for anyone looking to navigate the digital landscape with a reliable and skilled developer.