3258. Count Substrings That Satisfy K-Constraint I LeetCode Solution
In this guide, you will get 3258. Count Substrings That Satisfy K-Constraint I LeetCode Solution with the best time and space complexity. The solution to Count Substrings That Satisfy K-Constraint I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count Substrings That Satisfy K-Constraint I
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'.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
3258. Count Substrings That Satisfy K-Constraint I LeetCode Solution in C++
class Solution {
public:
int countKConstraintSubstrings(string s, int k) {
int ans = 0;
vector<int> count(2);
for (int l = 0, r = 0; r < s.length(); ++r) {
++count[s[r] - '0'];
while (count[0] > k && count[1] > k)
--count[s[l++] - '0'];
ans += r - l + 1;
}
return ans;
}
}; /* code provided by PROGIEZ */
3258. Count Substrings That Satisfy K-Constraint I LeetCode Solution in Java
class Solution {
public int countKConstraintSubstrings(String s, int k) {
int ans = 0;
int[] count = new int[2];
int l = 0;
for (int r = 0; r < s.length(); ++r) {
++count[s.charAt(r) - '0'];
while (count[0] > k && count[1] > k)
--count[s.charAt(l++) - '0'];
ans += r - l + 1;
}
return ans;
}
} // code provided by PROGIEZ
3258. Count Substrings That Satisfy K-Constraint I LeetCode Solution in Python
class Solution:
def countKConstraintSubstrings(self, s: str, k: int) -> int:
ans = 0
count = [0, 0]
l = 0
for r, c in enumerate(s):
count[int(c)] += 1
while min(count) > k:
count[int(s[l])] -= 1
l += 1
ans += r - l + 1
return ans # code by PROGIEZ
