Recuento de subarreglos de longitud K que contienen solo 1 en una string binaria determinada | conjunto 2

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

Ejemplos

Entrada: str = “0101000”, K=1
Salida: 2
Explicación: 0101000 -> Hay 2 subarreglos de longitud 1 que contienen solo 1s.

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

Enfoque: El problema dado también se puede resolver utilizando la técnica de la Ventana Deslizante . Cree una ventana de tamaño K inicialmente con la cuenta de 1 s desde el rango 0 hasta K-1 . Luego recorra la string desde el índice 1 hasta N-1 y reste el valor de i-1 y agregue el valor de i+K al conteo actual. Aquí, si el recuento actual es igual a K , incremente el posible recuento de subarreglos. 

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)
{
    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 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.

# 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# 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.

<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>

3

 Complejidad de tiempo: O(N), donde N es la longitud de la string. 

Espacio Auxiliar: O(1).