3258. Count Substrings That Satisfy K-Constraint using Rust

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
    }
}