Dada una string binaria de longitud N y un entero K, necesitamos averiguar cuántas substrings de esta string existen que contienen exactamente K.
Ejemplos:
Input : s = “10010”
K = 1
Output : 9
The 9 substrings containing one 1 are,
“1”, “10”, “100”, “001”, “01”, “1”,
“10”, “0010” and “010”
En este problema, necesitamos encontrar el recuento de substrings que contiene exactamente K o, en otras palabras, la suma de los dígitos en esas substrings es K. Primero creamos una array de suma de prefijos y hacemos un bucle sobre eso y nos detenemos cuando el valor de la suma es mayor o igual a K. Ahora, si la suma en el índice actual es (K + a), entonces sabemos que la suma de la substring, de todos esos índices donde la suma es (a), hasta el índice actual será K, por lo que el recuento de índices que tienen la suma (a), será agregarse al resultado. Este procedimiento se explica con un ejemplo a continuación,
string s = “100101” K = 2 prefix sum array = [1, 1, 1, 2, 2, 3] So, at index 3, we have prefix sum 2, Now total indices from where sum is 2, is 1 so result = 1 Substring considered = [“1001”] At index 4, we have prefix sum 2, Now total indices from where sum is 2, is 1 so result = 2 Substring considered = [“1001”, “10010”] At index 5, we have prefix sum 3, Now total indices from where sum is 2, is 3 so result = 5 Substring considered = [“1001”, “10010”, “00101”, “0101”, “101”]
Entonces, necesitamos rastrear dos cosas, la suma del prefijo y la frecuencia de la suma particular. En el código siguiente, en lugar de almacenar la suma de prefijos completa, solo se almacena la suma de prefijos en el índice actual utilizando una variable y la frecuencia de las sumas almacenadas en una array. La complejidad temporal total de la solución es O(N).
Implementación:
C++
// C++ program to find count of substring containing
// exactly K ones
#include <bits/stdc++.h>
using namespace std;
// method returns total number of substring having K ones
int countOfSubstringWithKOnes(string s, int K)
{
int N = s.length();
int res = 0;
int countOfOne = 0;
int freq[N + 1] = {0};
// initialize index having zero sum as 1
freq[0] = 1;
// loop over binary characters of string
for (int i = 0; i < N; i++) {
// update countOfOne variable with value
// of ith character
countOfOne += (s[i] - '0');
// if value reaches more than K, then
// update result
if (countOfOne >= K) {
// add frequency of indices, having
// sum (current sum - K), to the result
res += freq[countOfOne - K];
}
// update frequency of one's count
freq[countOfOne]++;
}
return res;
}
// Driver code to test above methods
int main()
{
string s = "10010";
int K = 1;
cout << countOfSubstringWithKOnes(s, K) << endl;
return 0;
}
Java
// Java program to find count of substring
// containing exactly K ones
import java.io.*;
public class GFG {
// method returns total number of
// substring having K ones
static int countOfSubstringWithKOnes(
String s, int K)
{
int N = s.length();
int res = 0;
int countOfOne = 0;
int []freq = new int[N+1];
// initialize index having zero
// sum as 1
freq[0] = 1;
// loop over binary characters
// of string
for (int i = 0; i < N; i++) {
// update countOfOne variable
// with value of ith character
countOfOne += (s.charAt(i) - '0');
// if value reaches more than
// K, then update result
if (countOfOne >= K) {
// add frequency of indices,
// having sum (current sum - K),
// to the result
res += freq[countOfOne - K];
}
// update frequency of one's count
freq[countOfOne]++;
}
return res;
}
// Driver code to test above methods
static public void main (String[] args)
{
String s = "10010";
int K = 1;
System.out.println(
countOfSubstringWithKOnes(s, K));
}
}
// This code is contributed by vt_m.
Python3
# Python 3 program to find count of
# substring containing exactly K ones
# method returns total number of
# substring having K ones
def countOfSubstringWithKOnes(s, K):
N = len(s)
res = 0
countOfOne = 0
freq = [0 for i in range(N + 1)]
# initialize index having
# zero sum as 1
freq[0] = 1
# loop over binary characters of string
for i in range(0, N, 1):
# update countOfOne variable with
# value of ith character
countOfOne += ord(s[i]) - ord('0')
# if value reaches more than K,
# then update result
if (countOfOne >= K):
# add frequency of indices, having
# sum (current sum - K), to the result
res += freq[countOfOne - K]
# update frequency of one's count
freq[countOfOne] += 1
return res
# Driver code
if __name__ == '__main__':
s = "10010"
K = 1
print(countOfSubstringWithKOnes(s, K))
# This code is contributed by
# Surendra_Gangwar
C#
// C# program to find count of substring
// containing exactly K ones
using System;
public class GFG {
// method returns total number of
// substring having K ones
static int countOfSubstringWithKOnes(
string s, int K)
{
int N = s.Length;
int res = 0;
int countOfOne = 0;
int []freq = new int[N+1];
// initialize index having zero
// sum as 1
freq[0] = 1;
// loop over binary characters
// of string
for (int i = 0; i < N; i++) {
// update countOfOne variable
// with value of ith character
countOfOne += (s[i] - '0');
// if value reaches more than
// K, then update result
if (countOfOne >= K) {
// add frequency of indices,
// having sum (current sum - K),
// to the result
res += freq[countOfOne - K];
}
// update frequency of one's count
freq[countOfOne]++;
}
return res;
}
// Driver code to test above methods
static public void Main ()
{
string s = "10010";
int K = 1;
Console.WriteLine(
countOfSubstringWithKOnes(s, K));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find count
// of substring containing
// exactly K ones
// method returns total number
// of substring having K ones
function countOfSubstringWithKOnes($s, $K)
{
$N = strlen($s);
$res = 0;
$countOfOne = 0;
$freq = array();
for ($i = 0; $i <= $N; $i++)
$freq[$i] = 0;
// initialize index
// having zero sum as 1
$freq[0] = 1;
// loop over binary
// characters of string
for ($i = 0; $i < $N; $i++)
{
// update countOfOne
// variable with value
// of ith character
$countOfOne += ($s[$i] - '0');
// if value reaches more
// than K, then update result
if ($countOfOne >= $K)
{
// add frequency of indices,
// having sum (current sum - K),
// to the result
$res = $res + $freq[$countOfOne - $K];
}
// update frequency
// of one's count
$freq[$countOfOne]++;
}
return $res;
}
// Driver code
$s = "10010";
$K = 1;
echo countOfSubstringWithKOnes($s, $K) ,"\n";
// This code is contributed by m_kit
?>
Javascript
<script>
// Javascript program to find count of
// substring containing exactly K ones
// Method returns total number of
// substring having K ones
function countOfSubstringWithKOnes(s, K)
{
let N = s.length;
let res = 0;
let countOfOne = 0;
let freq = new Array(N + 1);
freq.fill(0);
// Initialize index having zero
// sum as 1
freq[0] = 1;
// Loop over binary characters
// of string
for(let i = 0; i < N; i++)
{
// Update countOfOne variable
// with value of ith character
countOfOne += (s[i] - '0');
// If value reaches more than
// K, then update result
if (countOfOne >= K)
{
// Add frequency of indices,
// having sum (current sum - K),
// to the result
res += freq[countOfOne - K];
}
// Update frequency of one's count
freq[countOfOne]++;
}
return res;
}
// Driver code
let s = "10010";
let K = 1;
document.write(countOfSubstringWithKOnes(s, K));
// This code is contributed by suresh07
</script>
9
Complejidad temporal: O(N).
Espacio Auxiliar: O(N).
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA