Dada una string binaria str . La tarea es encontrar el tamaño del conjunto (contiene substrings únicas) de substrings tales que si hay una substring (supongamos que A ) de longitud n con un número par de 1 y también hay otra substring (supongamos que B ) del mismo longitud n y un número par de 1 y es inverso a A , entonces solo se consideraría A en el conjunto de strings.
Ejemplos:
Entrada: str = «10101»
Salida: 8
Explicación: Todas las substrings únicas de la string dada = {1, 0, 10, 01, 101, 010, 1010, 0101, 10101}.
En el conjunto anterior (1010, 0101) sigue la propiedad especial.
Por lo tanto, solo se considerarán 1010 en el conjunto dado.
Conjunto actualizado = A = {1, 0, 10, 01, 101, 010, 1010, 10101}.
Longitud de A=8Entrada: str = «10001»
Salida: 11
Explicación: Todas las substrings únicas de la string dada = {1, 0, 10, 01, 00, 100, 000, 001, 1000, 0001, 10001}.
En el conjunto anterior, ninguna string sigue a la propiedad especial. Longitud del conjunto = 11
Enfoque: siga estas dos reglas particulares para resolver el problema:
- Todas las strings en pares que no sigan una propiedad especial deben identificarse de forma única.
- Todas las strings en pares que siguen a una propiedad especial deben identificarse como una sola.
Entonces, para resolver este problema, use un conjunto de Lista de enteros donde cada lista contendría tres variables: {longitud, par, impar} . Además, use una variable de conteo que describa el conteo de 1 en la substring . Aquí ‘longitud’ describirá la longitud de la substring. Las variables pares e impares se utilizan para describir el recuento de 1 como par o impar siempre que se encuentre ‘0’ en la substring. Después de eso, agréguelo al conjunto de substrings y luego imprima el tamaño del conjunto.
¿POR QUÉ FUNCIONA ESTO?
Considere una string binaria con un número par de 1 y cada vez que se encuentre 0 en ella, vea cuántos 1 aparecen antes de ese 0 y, si es par, aumente el recuento de variables pares; de lo contrario, aumente el recuento de variables impares.
Supongamos que, cuando se encuentra 0 en una substring y hasta que tiene 1 pares, el resto también sería 1 (porque hemos considerado una string con 1 pares), de manera similar, si tenemos 1 impares hasta que encontremos 0, por lo tanto, el resto también sería 1 impar. Por lo tanto, la string inversa tendría la misma paridad (es decir, la cuenta de 1 como par o impar). Es por eso que no tomaría en consideración la string inversa.
Siga los pasos a continuación para resolver el problema:
- Inicialice el HashSet s[].
- Iterar sobre el rango [0, str.length()) usando la variable i y realizar las siguientes tareas:
- Inicialice el recuento de variables, pares e impares como 0 .
- Itere sobre el rango [0, a.length()) usando la variable j y realice las siguientes tareas:
- Si str[j] es igual a 1 , aumente el valor de count en 1.
- De lo contrario, si count%2 es igual a 0 , aumente el valor de par en 1 ; de lo contrario, el valor de impar en 1.
- Inicialice la variable len como j-i+1.
- Inicialice una nueva ArrayList x[].
- Agregue los valores de {largo, par, impar} a ArrayList x[].
- Agregue x[] al HashSet s[].
- Después de realizar los pasos anteriores, imprima el valor del tamaño del conjunto como respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find number of substrings
// fulfilling the condition
void find(string a)
{
// Initialize the hash-set
set<vector<int>> s;
// Traverse the string
for (int i = 0; i < a.length(); i++)
{
// Initialize the variables
int count = 0, even = 0, odd = 0;
for (int j = i; j < a.length();
j++)
{
// Check the condition
if (a[j] == '1')
{
count++;
}
else
{
if (count % 2 == 0)
{
even++;
}
else
{
odd++;
}
}
int len = j - i + 1;
vector<int> x;
x.push_back(len);
x.push_back(even);
x.push_back(odd);
s.insert(x);
}
}
// Print the result
cout << (s.size());
}
// Driver Code
int main()
{
string str = "10101";
find(str);
return 0;
}
// This code is contributed by Potta Lokesh
Java
// Java code to implement above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find number of substrings
// fulfilling the condition
public static void find(String a)
{
// Initialize the hash-set
HashSet<ArrayList<Integer> > s
= new HashSet<>();
// Traverse the string
for (int i = 0; i < a.length(); i++) {
// Initialize the variables
int count = 0, even = 0, odd = 0;
for (int j = i; j < a.length();
j++) {
// Check the condition
if (a.charAt(j) == '1') {
count++;
}
else {
if (count % 2 == 0) {
even++;
}
else {
odd++;
}
}
int len = j - i + 1;
ArrayList<Integer> x
= new ArrayList<>();
x.add(len);
x.add(even);
x.add(odd);
s.add(x);
}
}
// Print the result
System.out.println(s.size());
}
// Driver Code
public static void main(String[] args)
{
String str = "10101";
find(str);
}
}
Python3
# Python code to implement above approach # Function to find number of substrings # fulfilling the condition def find(a): # Initialize the hash-set s = set(); # Traverse the string for i in range(len(a)): # Initialize the variables count = 0; even = 0; odd = 0; for j in range(i,len(a)): # Check the condition if (a[j] == '1'): count += 1; else: if (count % 2 == 0): even += 1; else: odd += 1; length = j - i + 1; x = str(length)+str(even)+str(odd); s.add(x) # Print the result print(len(s)); # Driver Code if __name__ == '__main__': string = "10101"; find(string); # This code is contributed by 29AjayKumar
C#
// C# code to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
public class GFG{
// Function to find number of substrings
// fulfilling the condition
public static void find(String a)
{
// Initialize the hash-set
HashSet<string> s = new HashSet<string>();
string x;
// Traverse the string
for (int i = 0; i < a.Length; i++) {
// Initialize the variables
int count = 0, even = 0, odd = 0;
for (int j = i; j < a.Length;
j++) {
// Check the condition
if (a[j] == '1') {
count++;
}
else {
if (count % 2 == 0) {
even++;
}
else {
odd++;
}
}
int len = j - i + 1;
x = len.ToString() + even.ToString() +odd.ToString();
s.Add(x);
}
}
// Print the result
Console.Write(s.Count);
}
// Driver Code
public static void Main()
{
string str = "10101";
find(str);
}
}
// This code is contributed by Shubham Singh
Javascript
<script>
// Javascript code to implement above approach
// Function to find number of substrings
// fulfilling the condition
function find(a)
{
// Initialize the hash-set
let s = new Set();
let x = "";
// Traverse the string
for (let i = 0; i < a.length; i++) {
// Initialize the variables
let count = 0, even = 0, odd = 0;
for (let j = i; j < a.length;
j++) {
// Check the condition
if (a[j] == '1') {
count++;
}
else {
if (count % 2 == 0) {
even++;
}
else {
odd++;
}
}
let len = j - i + 1;
x = len.toString() + even.toString() + odd.toString();
s.add(x);
}
}
// Print the result
document.write(s.size);
}
// Driver Code
let str = "10101";
find(str);
// This code is contributed Saurabh Jaiswal
</script>
8
Complejidad de tiempo: O(N*N) donde N es la longitud de la string
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por lakshayr32 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA