Welcome to Subscribe On Youtube

3258. Count Substrings That Satisfy K-Constraint I

Description

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

Solutions

Solution 1: Sliding Window

We use two variables $\textit{cnt0}$ and $\textit{cnt1}$ to record the number of $0$s and $1$s in the current window, respectively. We use $\textit{ans}$ to record the number of substrings that satisfy the $k$ constraint, and $l$ to record the left boundary of the window.

When we move the window to the right, if the number of $0$s and $1$s in the window both exceed $k$, we need to move the window to the left until the number of $0$s and $1$s in the window are both no greater than $k$. At this point, all substrings in the window satisfy the $k$ constraint, and the number of such substrings is $r - l + 1$, where $r$ is the right boundary of the window. We add this count to $\textit{ans}$.

Finally, we return $\textit{ans}$.

The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.

  • class Solution {
        public int countKConstraintSubstrings(String s, int k) {
            int cnt0 = 0, cnt1 = 0;
            int ans = 0, l = 0;
            for (int r = 0; r < s.length(); ++r) {
                int x = s.charAt(r) - '0';
                cnt0 += x ^ 1;
                cnt1 += x;
                while (cnt0 > k && cnt1 > k) {
                    int y = s.charAt(l++) - '0';
                    cnt0 -= y ^ 1;
                    cnt1 -= y;
                }
                ans += r - l + 1;
            }
            return ans;
        }
    }
    
    
  • class Solution {
    public:
        int countKConstraintSubstrings(string s, int k) {
            int cnt0 = 0, cnt1 = 0;
            int ans = 0, l = 0;
            for (int r = 0; r < s.length(); ++r) {
                int x = s[r] - '0';
                cnt0 += x ^ 1;
                cnt1 += x;
                while (cnt0 > k && cnt1 > k) {
                    int y = s[l++] - '0';
                    cnt0 -= y ^ 1;
                    cnt1 -= y;
                }
                ans += r - l + 1;
            }
            return ans;
        }
    };
    
    
  • class Solution:
        def countKConstraintSubstrings(self, s: str, k: int) -> int:
            cnt0 = cnt1 = 0
            ans = l = 0
            for r, c in enumerate(s):
                cnt0 += int(c) ^ 1
                cnt1 += int(c)
                while cnt0 > k and cnt1 > k:
                    cnt0 -= int(s[l]) ^ 1
                    cnt1 -= int(s[l])
                    l += 1
                ans += r - l + 1
            return ans
    
    
  • func countKConstraintSubstrings(s string, k int) (ans int) {
    	cnt0, cnt1, l := 0, 0, 0
    	for r, c := range s {
    		x := int(c - '0')
    		cnt0 += x ^ 1
    		cnt1 += x
    		for cnt0 > k && cnt1 > k {
    			y := int(s[l] - '0')
    			cnt0 -= y ^ 1
    			cnt1 -= y
    			l++
    		}
    		ans += r - l + 1
    	}
    	return
    }
    
    
  • function countKConstraintSubstrings(s: string, k: number): number {
        let [cnt0, cnt1, ans, l] = [0, 0, 0, 0];
        for (let r = 0; r < s.length; ++r) {
            const x = s[r] === '1' ? 1 : 0;
            cnt0 += x ^ 1;
            cnt1 += x;
            while (cnt0 > k && cnt1 > k) {
                const y = s[l++] === '1' ? 1 : 0;
                cnt0 -= y ^ 1;
                cnt1 -= y;
            }
            ans += r - l + 1;
        }
        return ans;
    }
    
    

All Problems

All Solutions