Dada una string binaria str[] de tamaño N . La tarea es encontrar la substring balanceada más larga . Una substring está balanceada si contiene un número igual de 0 y 1 .
Ejemplos:
Entrada: str = “110101010”
Salida: 10101010
Explicación: La substring formada contiene el mismo recuento de 1 y 0, es decir, el recuento de 1 y 0 es igual a 4.Entrada: str = “0000”
Salida: -1
Enfoque ingenuo: una solución simple es usar dos bucles anidados para generar cada substring . Y un tercer ciclo para contar un número de 0 y 1 en la substring actual . Luego imprima la substring más larga entre ellos.
Complejidad de tiempo: O(N^3)
Espacio auxiliar: O(1)
Solución eficiente: con la ayuda del cálculo previo, almacene la diferencia entre el recuento de 0 y el recuento de 1 desde el inicio hasta el índice actual. Esta diferencia se puede usar para determinar la substring más larga con 0 y 1 iguales , como la distancia más larga entre cualquier valor duplicado en la array de diferencia. Utilice un hash basado en mapas para realizar cálculos previos. Siga los pasos a continuación para resolver el problema:
- Inicialice el mapa <int, int> m[].
- Establezca el valor de m[0] como -1.
- Inicialice las variables count_0, count_1, res, start y end .
- Recorra la string str[] usando la variable i y realice las siguientes tareas:
- Lleve un registro de los recuentos de 1 y 0 como count_1 y count_0 respectivamente.
- Vea si la diferencia actual entre count_1 y count_0 ya está en el mapa m[] o no. En caso afirmativo, realice las siguientes tareas:
- La substring de la aparición anterior y el índice actual tiene el mismo número de 0 y 1 .
- Si la longitud de la substring encontrada actual es mayor que res , establezca la substring encontrada como la respuesta hasta el momento.
- Si aparece por primera vez, almacene la diferencia actual y el índice actual en el mapa, es decir, m[count_1 – count_0] es igual a i .
- Si count_0 y count_1 son ambos 0, imprima -1.
- De lo contrario, imprima la substring de principio a fin.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ for finding length
// of longest balanced substring
#include <bits/stdc++.h>
using namespace std;
// Returns length of the longest substring
// with equal number of zeros and ones.
string stringLen(string str)
{
// Create a map to store differences
// between counts of 1s and 0s.
map<int, int> m;
// Initially difference is 0.
m[0] = -1;
int count_0 = 0, count_1 = 0;
int start, end, res = 0;
for (int i = 0; i < str.size(); i++) {
// Keeping track of counts of
// 0s and 1s.
if (str[i] == '0')
count_0++;
else
count_1++;
// If difference between current counts
// already exists, then substring between
// previous and current index has same
// no. of 0s and 1s. Update result if this
// substring is more than current result.
if (m.find(count_1 - count_0) != m.end()) {
if ((i - m[count_1 - count_0]) > res) {
start = m.find(
count_1 - count_0)
->second;
end = i;
res = end - start;
}
}
// If current difference
// is seen first time.
else
m[count_1 - count_0] = i;
}
if (count_0 == 0 || count_1 == 0)
return "-1";
// Return the substring
// between found indices
return str.substr(start + 1, end + 1);
}
// Driver Code
int main()
{
string str = "110101010";
cout << stringLen(str);
return 0;
}
Java
// Java code for the above approach
import java.io.*;
class GFG
{
// Returns length of the longest substring
// with equal number of zeros and ones.
static String stringLen(String str)
{
// Create a map to store differences
// between counts of 1s and 0s.
int [] m = new int[100000];
// Initially difference is 0.
m[0] = -1;
int count_0 = 0; int count_1 = 0;
int start = 0; int end = 0; int res = 0;
for (int i = 0; i < str.length(); i++) {
// Keeping track of counts of
// 0s and 1s.
if (str.charAt(i) == '0')
count_0++;
else
count_1++;
// If difference between current counts
// already exists, then substring between
// previous and current index has same
// no. of 0s and 1s. Update result if this
// substring is more than current result.
if (m[count_1 - count_0]!= 0) {
if ((i - m[count_1 - count_0]) > res) {
start = m[count_1 - count_0];
end = i;
res = end - start;
}
}
// If current difference
// is seen first time.
else
m[count_1 - count_0] = i;
}
if (count_0 == 0 || count_1 == 0)
return "-1";
// Return the substring
// between found indices
return str.substring(start , end + 2);
}
// Driver Code
public static void main (String[] args)
{
String str = "110101010";
System.out.println(stringLen(str));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python for finding length
# of longest balanced substring
# Returns length of the longest substring
# with equal number of zeros and ones.
def stringLen (str) :
# Create a map to store differences
# between counts of 1s and 0s.
m = {}
# Initially difference is 0.
m[0] = -1
count_0 = 0
count_1 = 0
res = 0
for i in range(len(str)):
# Keeping track of counts of
# 0s and 1s.
if (str[i] == '0'):
count_0 += 1
else:
count_1 += 1
# If difference between current counts
# already exists, then substring between
# previous and current index has same
# no. of 0s and 1s. Update result if this
# substring is more than current result.
if ((count_1 - count_0) in m):
if ((i - m[count_1 - count_0]) > res):
start = m[(count_1 - count_0)]
end = i
res = end - start
# If current difference
# is seen first time.
else:
m[count_1 - count_0] = i
if (count_0 == 0 or count_1 == 0):
return "-1"
# Return the substring
# between found indices
return str[start + 1 : start + 1 + end + 1]
# Driver Code
str = "110101010"
print(stringLen(str))
# This code is contributed by Saurabh Jaiswal
C#
// C# code for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Returns length of the longest substring
// with equal number of zeros and ones.
static string stringLen(string str)
{
// Create a map to store differences
// between counts of 1s and 0s.
int []m = new int[100000];
// Initially difference is 0.
m[0] = -1;
int count_0 = 0; int count_1 = 0;
int start = 0; int end = 0; int res = 0;
for (int i = 0; i < str.Length; i++) {
// Keeping track of counts of
// 0s and 1s.
if (str[i] == '0')
count_0++;
else
count_1++;
// If difference between current counts
// already exists, then substring between
// previous and current index has same
// no. of 0s and 1s. Update result if this
// substring is more than current result.
if (m[count_1 - count_0]!= 0) {
if ((i - m[count_1 - count_0]) > res) {
start = m[count_1 - count_0];
end = i;
res = end - start;
}
}
// If current difference
// is seen first time.
else
m[count_1 - count_0] = i;
}
if (count_0 == 0 || count_1 == 0)
return "-1";
// Return the substring
// between found indices
return str.Substring(start, end - start + 2);
}
// Driver Code
public static void Main ()
{
string str = "110101010";
Console.Write(stringLen(str));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript for finding length
// of longest balanced substring
// Returns length of the longest substring
// with equal number of zeros and ones.
const stringLen = (str) => {
// Create a map to store differences
// between counts of 1s and 0s.
let m = {};
// Initially difference is 0.
m[0] = -1;
let count_0 = 0, count_1 = 0;
let start, end, res = 0;
for (let i = 0; i < str.length; i++) {
// Keeping track of counts of
// 0s and 1s.
if (str[i] == '0')
count_0++;
else
count_1++;
// If difference between current counts
// already exists, then substring between
// previous and current index has same
// no. of 0s and 1s. Update result if this
// substring is more than current result.
if ((count_1 - count_0) in m) {
if ((i - m[count_1 - count_0]) > res) {
start = m[(count_1 - count_0)];
end = i;
res = end - start;
}
}
// If current difference
// is seen first time.
else
m[count_1 - count_0] = i;
}
if (count_0 == 0 || count_1 == 0)
return "-1";
// Return the substring
// between found indices
return str.substring(start + 1, start + 1 + end + 1);
}
// Driver Code
let str = "110101010";
document.write(stringLen(str));
// This code is contributed by rakeshsahni
</script>
Producción
10101010
Complejidad temporal: O(N)
Espacio auxiliar: O(N)