Given binary string str, the task is to find the count of K length subarrays containing only 1s.
Examples
Input: str = “0101000”, K=1
Output: 2
Explanation: 0101000 -> There are 2 subarrays of length 1 containing only 1s.Input: str = “11111001”, K=3
Output: 3
Approach: The given problem can also be solved by using the Sliding Window technique. Create a window of size K initially with the count of 1s from range 0 to K-1. Then traverse the string from index 1 to N-1 and subtract the value of i-1 and add the value of i+K to the current count. Here if the current count is equal to K, increment the possible count of subarrays.
Below is the implementation of the above approach.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the count of all possible // k length subarrays int get(string s, int k) { int n = s.length(); int cntOf1s = 0; for (int i = 0; i < k; i++) if (s[i] == '1') cntOf1s++; int ans = cntOf1s == k ? 1 : 0; for (int i = 1; i < n; i++) { cntOf1s = cntOf1s - (s[i - 1] - '0') + (s[i + k - 1] - '0'); if (cntOf1s == k) ans++; } return ans; } // Driver code int main() { string str = "0110101110"; int K = 2; cout << get(str, K) << endl; return 0; } |
Java
// Java code to implement above approach import java.util.*; public class GFG { // Function to find the count of all possible // k length subarrays static int get(String s, int k) { int n = s.length(); int cntOf1s = 0; for (int i = 0; i < k; i++) { if (s.charAt(i) == '1') { cntOf1s++; } } int ans = cntOf1s == k ? 1 : 0; for (int i = 1; i < n; i++) { if(i + k - 1 < n) { cntOf1s = cntOf1s - (s.charAt(i - 1) - '0') + (s.charAt(i + k - 1) - '0'); } if (cntOf1s == k) ans++; } return ans; } // Driver code public static void main(String args[]) { String str = "0110101110"; int K = 2; System.out.println(get(str, K)); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# Python code to implement above approach # Function to find the count of all possible # k length subarrays def get(s, k): n = len(s); cntOf1s = 0; for i in range(0,k): if (s[i] == '1'): cntOf1s += 1; ans = i if (cntOf1s == k) else 0; for i in range(1, n): if (i + k - 1 < n): cntOf1s = cntOf1s - (ord(s[i - 1]) - ord('0')) + (ord(s[i + k - 1]) - ord('0')); if (cntOf1s == k): ans += 1; return ans; # Driver code if __name__ == '__main__': str = "0110101110"; K = 2; print(get(str, K)); # This code is contributed by 29AjayKumar |
C#
// C# code to implement above approach using System; public class GFG { // Function to find the count of all possible // k length subarrays static int get(string s, int k) { int n = s.Length; int cntOf1s = 0; for (int i = 0; i < k; i++) { if (s[i] == '1') { cntOf1s++; } } int ans = cntOf1s == k ? 1 : 0; for (int i = 1; i < n; i++) { if (i + k - 1 < n) { cntOf1s = cntOf1s - (s[i - 1] - '0') + (s[i + k - 1] - '0'); } if (cntOf1s == k) ans++; } return ans; } // Driver code public static void Main() { string str = "0110101110"; int K = 2; Console.WriteLine(get(str, K)); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach // Function to find the count of all possible // k length subarrays function get(s, k) { let n = s.length; let cntOf1s = 0; for (let i = 0; i < k; i++) if (s[i] == '1') cntOf1s++; let ans = cntOf1s == k ? 1 : 0; for (let i = 1; i < n; i++) { cntOf1s = cntOf1s - (s[i - 1] - '0') + (s[i + k - 1] - '0'); if (cntOf1s == k) ans++; } return ans; } // Driver code let str = "0110101110"; let K = 2; document.write(get(str, K) + '<br>') // This code is contributed by Potta Lokesh </script> |
Output
3
Time Complexity: O(N), Where N is the length of the string.
Auxiliary Space: O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
