Recuento de subarreglos de longitud K que contienen solo 1 en una string binaria dada

Dada una string binaria str , la tarea es encontrar el conteo de K subarreglos de longitud que contienen solo 1s.

Ejemplos:

Entrada: str = “0101000”, K=1
Salida: 2
Explicación: 0 1 0 1 000 -> Hay 2 subarreglos con 1 unos

Entrada: str = “11111001”, K=3
Salida: 3

Enfoque : La tarea se puede resolver haciendo un seguimiento del tamaño de los grupos de grupos consecutivos . Una vez que obtenemos groupSize , podemos deducir que el número de posibles subarreglos de longitud k , y todos los 1 , son groupSize – k + 1 .

Siga los pasos a continuación para resolver el problema:

• Iterar sobre la string binaria desde el principio
• Incremente el conteo, si se encuentra 1 , y en un punto donde viene 0 .
• Almacene el conteo actual para obtener el tamaño de grupo de 1 consecutivos y reinicie el conteo a 0.
• Agregue el recuento de posibles subarreglos de tamaño k en este tamaño de grupo usando la relación tamaño de grupo – k + 1
• Devuelve la suma final de la cuenta.

A continuación se muestra la implementación del enfoque anterior:

// 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)
{
    // Add dummy character at last to handle
    // edge cases, where string ends with '1'
    s += '0';
    int n = s.length();
 
    int cnt = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1')
            cnt++;
        else {
            if (cnt >= k) {
                ans += (cnt - k + 1);
            }
            cnt = 0;
        }
    }
    return ans;
}
 
// Driver code
int main()
{
    string str = "0101000";
    int K = 1;
    cout << get(str, K) << endl;
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the count of all possible
// k length subarrays
static int get(String s, int k)
{
   
    // Add dummy character at last to handle
    // edge cases, where String ends with '1'
    s += '0';
    int n = s.length();
 
    int cnt = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == '1')
            cnt++;
        else {
            if (cnt >= k) {
                ans += (cnt - k + 1);
            }
            cnt = 0;
        }
    }
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    String str = "0101000";
    int K = 1;
    System.out.print(get(str, K) +"\n");
}
}
 
// This code is contributed by Rajput-Ji

# Python code for the above approach
 
# Function to find the count of all possible
# k length subarrays
def get(s, k):
 
    # Add dummy character at last to handle
    # edge cases, where string ends with '1'
    s += '0'
    n = len(s)
 
    cnt = 0
    ans = 0
    for i in range(n):
        if (s[i] == '1'):
            cnt += 1
        else:
            if (cnt >= k):
                ans += (cnt - k + 1)
            cnt = 0
    return ans
 
# Driver code
str = "0101000"
K = 1
print(get(str, K))
 
# This code is contributed by Saurabh Jaiswal

// C# program for the above approach
using System;
class GFG
{
   
    // Function to find the count of all possible
    // k length subarrays
    static int get(string s, int k)
    {
       
        // Add dummy character at last to handle
        // edge cases, where string ends with '1'
        s += '0';
        int n = s.Length;
 
        int cnt = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '1')
                cnt++;
            else {
                if (cnt >= k) {
                    ans += (cnt - k + 1);
                }
                cnt = 0;
            }
        }
        return ans;
    }
 
    // Driver code
    public static void Main()
    {
        string str = "0101000";
        int K = 1;
        Console.WriteLine(get(str, K));
    }
}
 
// This code is contributed by ukasp.

<script>
    // JavaScript code for the above approach
 
    // Function to find the count of all possible
    // k length subarrays
    function get(s, k)
    {
     
      // Add dummy character at last to handle
      // edge cases, where string ends with '1'
      s += '0';
      let n = s.length;
 
      let cnt = 0, ans = 0;
      for (let i = 0; i < n; i++) {
        if (s[i] == '1')
          cnt++;
        else {
          if (cnt >= k) {
            ans += (cnt - k + 1);
          }
          cnt = 0;
        }
      }
      return ans;
    }
 
    // Driver code
    let str = "0101000";
    let K = 1;
    document.write(get(str, K) + '<br>');
 
  // This code is contributed by Potta Lokesh
  </script>

2

Complejidad de Tiempo : O(N) 
Espacio Auxiliar : O(1)