Skip to content

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

Thinking

The \(k\)-constraint asks that a substring has at most \(k\) zeros or at most \(k\) ones. \(n\le 50\) would allow listing substrings, but the constraint is monotone in the right end: once both counts exceed \(k\), the left end must move.

A sliding window keeps \(c_0,c_1\) and shrinks on overflow. Every substring ending at \(r\) with left end in \([l,r]\) is then valid, hence \(r-l+1\) of them. One linear pass.

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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int countKConstraintSubstrings(string s, int k) {
        int cnt[2]{};
        int ans = 0, l = 0;
        for (int r = 0; r < s.length(); ++r) {
            cnt[s[r] - '0']++;
            while (cnt[0] > k && cnt[1] > k) {
                cnt[s[l++] - '0']--;
            }
            ans += r - l + 1;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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
    }
}

Comments