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 mostk
. - The number of
1
's in the string is at mostk
.
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; }