Dada una string binaria S de longitud N y un entero par K , la tarea es comprobar si todas las substrings de longitud K contienen el mismo número de 0 s y 1 s. Si es cierto, escriba «Sí». De lo contrario, escriba “No”.
Ejemplos:
Entrada: S = “101010”, K = 2
Salida: Sí
Explicación:
Dado que todas las substrings de longitud 2 tienen el mismo número de 0 y 1, la respuesta es Sí.Entrada: S = «101011», K = 4
Salida: No
Explicación:
Dado que la substring «1011» tiene un recuento desigual de 0 y 1, la respuesta es No.
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las substrings de longitud K y verificar si contiene un recuento igual de 1 y 0 o no.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: la observación principal para optimizar el enfoque anterior es que, para que la string S tenga un recuento igual de 0 y 1 en substrings de longitud K , S[i] debe ser igual a S[i + k] . Siga los pasos a continuación para resolver el problema:
- Recorra la string y para cada i -ésimo carácter, verifique si S[i] = S[j] donde (i == (j % k))
- Si se encuentra que es falso en cualquier momento, escriba «No».
- De lo contrario, verifique la primera substring de longitud K y si contiene un recuento igual de 1 y 0 o no. Si se encuentra que es cierto, escriba «Sí». De lo contrario, escriba “No”.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to check if the substring
// of length K has equal 0 and 1
int check(string& s, int k)
{
int n = s.size();
// Traverse the string
for (int i = 0; i < k; i++) {
for (int j = i; j < n; j += k) {
// Check if every K-th character
// is the same or not
if (s[i] != s[j])
return false;
}
}
int c = 0;
// Traverse substring of length K
for (int i = 0; i < k; i++) {
// If current character is 0
if (s[i] == '0')
// Increment count
c++;
// Otherwise
else
// Decrement count
c--;
}
// Check for equal 0s and 1s
if (c == 0)
return true;
else
return false;
}
// Driver code
int main()
{
string s = "101010";
int k = 2;
if (check(s, k))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
Java
// Java program for
// the above approach
import java.util.*;
class GFG{
// Function to check if the substring
// of length K has equal 0 and 1
static boolean check(String s, int k)
{
int n = s.length();
// Traverse the String
for (int i = 0; i < k; i++)
{
for (int j = i; j < n; j += k)
{
// Check if every K-th character
// is the same or not
if (s.charAt(i) != s.charAt(j))
return false;
}
}
int c = 0;
// Traverse subString of length K
for (int i = 0; i < k; i++)
{
// If current character is 0
if (s.charAt(i) == '0')
// Increment count
c++;
// Otherwise
else
// Decrement count
c--;
}
// Check for equal 0s and 1s
if (c == 0)
return true;
else
return false;
}
// Driver code
public static void main(String[] args)
{
String s = "101010";
int k = 2;
if (check(s, k))
System.out.print("Yes" + "\n");
else
System.out.print("No" + "\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach
# Function to check if the substring
# of length K has equal 0 and 1
def check(s, k):
n = len(s)
# Traverse the string
for i in range(k):
for j in range(i, n, k):
# Check if every K-th character
# is the same or not
if (s[i] != s[j]):
return False
c = 0
# Traverse substring of length K
for i in range(k):
# If current character is 0
if (s[i] == '0'):
# Increment count
c += 1
# Otherwise
else:
# Decrement count
c -= 1
# Check for equal 0s and 1s
if (c == 0):
return True
else:
return False
# Driver code
s = "101010"
k = 2
if (check(s, k) != 0):
print("Yes")
else:
print("No")
# This code is contributed by sanjoy_62
C#
// C# program for
// the above approach
using System;
class GFG{
// Function to check if the substring
// of length K has equal 0 and 1
static bool check(String s, int k)
{
int n = s.Length;
// Traverse the String
for (int i = 0; i < k; i++)
{
for (int j = i; j < n; j += k)
{
// Check if every K-th character
// is the same or not
if (s[i] != s[j])
return false;
}
}
int c = 0;
// Traverse subString of length K
for (int i = 0; i < k; i++)
{
// If current character is 0
if (s[i] == '0')
// Increment count
c++;
// Otherwise
else
// Decrement count
c--;
}
// Check for equal 0s and 1s
if (c == 0)
return true;
else
return false;
}
// Driver code
public static void Main(String[] args)
{
String s = "101010";
int k = 2;
if (check(s, k))
Console.Write("Yes" + "\n");
else
Console.Write("No" + "\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program for the
// above approach
// Function to check if the substring
// of length K has equal 0 and 1
function check(s, k)
{
let n = s.length;
// Traverse the String
for (let i = 0; i < k; i++)
{
for (let j = i; j < n; j += k)
{
// Check if every K-th character
// is the same or not
if (s[i] != s[j])
return false;
}
}
let c = 0;
// Traverse subString of length K
for (let i = 0; i < k; i++)
{
// If current character is 0
if (s[i]== '0')
// Increment count
c++;
// Otherwise
else
// Decrement count
c--;
}
// Check for equal 0s and 1s
if (c == 0)
return true;
else
return false;
}
// Driver Code
let s = "101010";
let k = 2;
if (check(s, k))
document.write("Yes" + "<br/>");
else
document.write("No");
// This code is contributed by target_2.
</script>
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ayushnemmaniwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA