Dada una string binaria str[] , la tarea es encontrar todos los subarreglos de longitud K posibles que contengan solo 1 e imprimir su índice inicial y final.
Ejemplos:
Entrada: str = “0101000”, K=1
Salida:
1 1
3 3
Explicación: Las substrings en las posiciones 1 y 3 son las substrings con valor 1.Entrada: str = “11111001”, K=3
Salida:
0 2
1 3
2 4
Enfoque: El problema dado se puede resolver con la ayuda de la técnica de la Ventana Deslizante . Cree una ventana de tamaño K inicialmente con un conteo de 1s 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. Si el conteo actual es igual a K , imprima el valor de i e i+k-1 como uno de los posibles subarreglos. Siga los pasos a continuación para resolver el problema:
- Inicialice la variable cntOf1s como 0.
- Itere sobre el rango [0, K) usando la variable i y realice las siguientes tareas:
- Si s[i] es igual a 1 , aumente el valor de cntOf1s en 1.
- Si cntOf1s es igual a K , imprima la substring actual como una de las respuestas.
- Itere sobre el rango [1, N) usando la variable i y realice las siguientes tareas:
- Reduzca el valor desde la izquierda y agregue desde la derecha a la variable cntOf1s si los caracteres en esa posición son 1.
- Si el valor de cntOf1s es igual a K , imprima la substring actual como respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find all possible
// k length subarrays
void get(string s, int k)
{
int n = s.length();
int cntOf1s = 0;
// Initial window
for (int i = 0; i < k; i++)
if (s[i] == '1')
cntOf1s++;
if (cntOf1s == k)
cout << 0 << " " << k - 1 << endl;
// Traverse the string
for (int i = 1; i < n; i++) {
// Subtract the value from the left and
// add from the right
cntOf1s = cntOf1s - (s[i - 1] - '0')
+ (s[i + k - 1] - '0');
// Check the condition
if (cntOf1s == k)
cout << i << " " << i + k - 1 << endl;
}
}
// Driver Code
int main()
{
string str = "0110101110";
int K = 2;
get(str, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find all possible
// k length subarrays
static void get(char[] s, int k)
{
int n = s.length;
int cntOf1s = 0;
// Initial window
for (int i = 0; i < k; i++)
if (s[i] == '1')
cntOf1s++;
if (cntOf1s == k)
System.out.print(0+ " " + (k - 1 )+"\n");
// Traverse the String
for (int i = 1; i < n && (i + k - 1)<n; i++) {
// Subtract the value from the left and
// add from the right
cntOf1s = cntOf1s - (s[i - 1] - '0')
+ (s[i + k - 1] - '0');
// Check the condition
if (cntOf1s == k)
System.out.print(i+ " " + (i + k - 1 )+"\n");
}
}
// Driver Code
public static void main(String[] args)
{
String str = "0110101110";
int K = 2;
get(str.toCharArray(), K);
}
}
// This code is contributed by 29AjayKumar
Python3
# python3 program for the above approach
# Function to find all possible
# k length subarrays
def get(s, k):
n = len(s)
cntOf1s = 0
# Initial window
for i in range(0, k):
if (s[i] == '1'):
cntOf1s += 1
if (cntOf1s == k):
print(f"{0} {k - 1}")
# Traverse the string
for i in range(1, n - k + 1):
# Subtract the value from the left and
# add from the right
cntOf1s = cntOf1s - (ord(s[i - 1]) - ord('0')) + \
(ord(s[i + k - 1]) - ord('0'))
# Check the condition
if (cntOf1s == k):
print(f"{i} {i + k - 1}")
# Driver Code
if __name__ == "__main__":
str = "0110101110"
K = 2
get(str, K)
# This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find all possible
// k length subarrays
static void get(char[] s, int k)
{
int n = s.Length;
int cntOf1s = 0;
// Initial window
for (int i = 0; i < k; i++)
if (s[i] == '1')
cntOf1s++;
if (cntOf1s == k)
Console.Write(0 + " " + (k - 1) + "\n");
// Traverse the String
for (int i = 1; i < n && (i + k - 1) < n; i++)
{
// Subtract the value from the left and
// add from the right
cntOf1s = cntOf1s - (s[i - 1] - '0')
+ (s[i + k - 1] - '0');
// Check the condition
if (cntOf1s == k)
Console.Write(i + " " + (i + k - 1) + "\n");
}
}
// Driver Code
public static void Main()
{
String str = "0110101110";
int K = 2;
get(str.ToCharArray(), K);
}
}
// This code is contributed by Saurabh Jaiswal
Javascript
<script>
// JavaScript code for the above approach
// Function to find all possible
// k length subarrays
function get(s, k) {
let n = s.length;
let cntOf1s = 0;
// Initial window
for (let i = 0; i < k; i++)
if (s[i] == '1')
cntOf1s++;
if (cntOf1s == k)
document.write(0 + ' ' + (k - 1) + '<br>');
// Traverse the string
for (let i = 1; i < n; i++) {
// Subtract the value from the left and
// add from the right
cntOf1s = cntOf1s - (s[i - 1].charCodeAt(0) - '0'.charCodeAt(0))
+ (s[i + k - 1].charCodeAt(0) - '0'.charCodeAt(0));
// Check the condition
if (cntOf1s == k)
document.write(i + ' ' + (i + k - 1) + '<br>');
}
}
// Driver Code
let str = "0110101110";
let K = 2;
get(str, K);
// This code is contributed by Potta Lokesh
</script>
Producción
1 2 6 7 7 8
Complejidad temporal: O(N)
Espacio auxiliar: O(1)