Compute the Count of K Length Subarrays Containing Only 1s in Binary String

Approach

First, we will count the size of consecutive ones; after that, we will compute the count of k length subarrays from it.

Steps

• Add dummy character at last to handle the edge case where the string ends with ‘1’.
   
• Iterate the binary string from the start.
   
• Increment the count is ‘1’ is found during iteration.
   
• As soon as we see ‘0’, store the current count and initialize the count to 0 again.
   
• Add the count of k length subarray in this group size using relation group size – k + 1.
   
• Print the final count.
   

Also see, Euclid GCD Algorithm

Implementation

import java.util.*;

class Solution{

   // To count the k length subarrays
   static int count(String s, int k)
  {

      // If string ends with '1'
      s += '0';
      int n = s.length();

      int c = 0, ret = 0;
      for (int i = 0; i < n; i++) {
           if (s.charAt(i) == '1')
                c++;
           else {
              if (c >= k) {
                ret += (c - k + 1);
           }
           c = 0;
           }
      }
  return ret;
 }

// Main Function
public static void main(String[] args)
{
   String str = "1111110";
   int K = 3;
   System.out.print(count(str, K) +"\n");
}
}

You can also try this code with Online Java Compiler

Run Code

Output

4

You can also try this code with Online Java Compiler

Run Code

Complexities

Time Complexity: The time complexity for this approach is O(n), where n is the length of the binary string.

Space Complexity: O(1) is the space complexity.

Check out this problem - Subarray With 0 Sum

FAQs

1. What is the time complexity to solve this problem?
   The time taken by the normal mathematical implementation is O(n), where n is the length of the binary string.
    
2. What do you mean by subarray?
   An array can be divided into subarrays, which are the contiguous part of it.

Key Takeaways

In this blog, we have covered the following:

• What the problem is, along with the example.
• Approach to ponder upon.
• Implementation in the Java language.

Before stepping into this problem, you can try problems similar to this concept like Arithmetic Subarrays, Subarray Sums I, and many more.

Coding Ninjas Studio is a one-stop destination for various DSA questions typically asked in interviews to practice more such problems.

Happy Coding!!!