Dada una string binaria, busque la substring más larga que contenga 1 más que 0.
Ejemplos:
Input : 1010 Output : 3 Substring 101 has 1 occurring more number of times than 0. Input : 101100 Output : 5 Substring 10110 has 1 occurring more number of times than 0.
Una solución simple es considerar una por una todas las substrings y verificar si esa substring tiene un conteo de 1 más que 0. Si el conteo es más que comparar su longitud con la substring de longitud máxima encontrada hasta ahora. La complejidad temporal de esta solución es O(n^2).
un eficienteLa solución es usar hashing. La idea es encontrar la suma de las cuerdas recorridas hasta ahora. Agregue 1 al resultado si el carácter actual es ‘1’; de lo contrario, reste 1. Ahora el problema se reduce a encontrar el subarreglo más grande que tenga una suma mayor que cero. Para encontrar el subarreglo más grande que tiene una suma mayor que cero, verificamos el valor de la suma. Si sum es mayor que cero, entonces el subarreglo más grande con una suma mayor que cero es arr[0..i]. Si la suma es menor que cero, encuentre el tamaño del subarreglo arr[j+1..i], donde j es el índice hasta el cual la suma del subarreglo arr[0..j] es suma -1 y j < i y compare ese tamaño con el tamaño de subarreglo más grande encontrado hasta ahora. Para encontrar el índice j, almacene valores de sum para arr[0..j] en la tabla hash para todos los 0 <= j <= i. Puede haber una posibilidad de que un valor dado de sum se repita.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find largest substring
// having count of 1s more than count
// count of 0s.
#include <bits/stdc++.h>
using namespace std;
// Function to find longest substring
// having count of 1s more than count
// of 0s.
int findLongestSub(string bin)
{
int n = bin.length(), i;
// To store sum.
int sum = 0;
// To store first occurrence of each
// sum value.
unordered_map<int, int> prevSum;
// To store maximum length.
int maxlen = 0;
// To store current substring length.
int currlen;
for (i = 0; i < n; i++) {
// Add 1 if current character is 1
// else subtract 1.
if (bin[i] == '1')
sum++;
else
sum--;
// If sum is positive, then maximum
// length substring is bin[0..i]
if (sum > 0) {
maxlen = i + 1;
}
// If sum is negative, then maximum
// length substring is bin[j+1..i], where
// sum of substring bin[0..j] is sum-1.
else if (sum <= 0) {
if (prevSum.find(sum - 1) != prevSum.end()) {
currlen = i - prevSum[sum - 1];
maxlen = max(maxlen, currlen);
}
}
// Make entry for this sum value in hash
// table if this value is not present.
if (prevSum.find(sum) == prevSum.end())
prevSum[sum] = i;
}
return maxlen;
}
// Driver code
int main()
{
string bin = "1010";
cout << findLongestSub(bin);
return 0;
}
Java
// Java program to find largest substring
// having count of 1s more than count
// count of 0s.
import java.util.HashMap;
class GFG
{
// Function to find longest substring
// having count of 1s more than count
// of 0s.
static int findLongestSub(String bin)
{
int n = bin.length(), i;
// To store sum.
int sum = 0;
// To store first occurrence of each
// sum value.
HashMap<Integer,
Integer> prevSum = new HashMap<>();
// To store maximum length.
int maxlen = 0;
// To store current substring length.
int currlen;
for (i = 0; i < n; i++)
{
// Add 1 if current character is 1
// else subtract 1.
if (bin.charAt(i) == '1')
sum++;
else
sum--;
// If sum is positive, then maximum
// length substring is bin[0..i]
if (sum > 0)
{
maxlen = i + 1;
}
// If sum is negative, then maximum
// length substring is bin[j+1..i], where
// sum of substring bin[0..j] is sum-1.
else if (sum <= 0)
{
if (prevSum.containsKey(sum - 1))
{
currlen = i - (prevSum.get(sum - 1) == null ? 1 :
prevSum.get(sum - 1));
maxlen = Math.max(maxlen, currlen);
}
}
// Make entry for this sum value in hash
// table if this value is not present.
if (!prevSum.containsKey(sum))
prevSum.put(sum, i);
}
return maxlen;
}
// Driver code
public static void main(String[] args)
{
String bin = "1010";
System.out.println(findLongestSub(bin));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python 3 program to find largest substring
# having count of 1s more than count
# count of 0s.
# Function to find longest substring
# having count of 1s more than count
# of 0s.
def findLongestSub(bin1):
n = len(bin1)
# To store sum.
sum = 0
# To store first occurrence of each
# sum value.
prevSum = {i:0 for i in range(n)}
# To store maximum length.
maxlen = 0
# To store current substring length.
for i in range(n):
# Add 1 if current character is 1
# else subtract 1.
if (bin1[i] == '1'):
sum += 1
else:
sum -= 1
# If sum is positive, then maximum
# length substring is bin1[0..i]
if (sum > 0):
maxlen = i + 1
# If sum is negative, then maximum
# length substring is bin1[j+1..i], where
# sum of substring bin1[0..j] is sum-1.
elif (sum <= 0):
if ((sum - 1) in prevSum):
currlen = i - prevSum[sum - 1]
maxlen = max(maxlen, currlen)
# Make entry for this sum value in hash
# table if this value is not present.
if ((sum) not in prevSum):
prevSum[sum] = i
return maxlen
# Driver code
if __name__ == '__main__':
bin1 = "1010"
print(findLongestSub(bin1))
# This code is contributed by
# Surendra_Gangwar
C#
// C# program to find largest substring
// having count of 1s more than count
// count of 0s.
using System;
using System.Collections.Generic;
class GFG
{
// Function to find longest substring
// having count of 1s more than count
// of 0s.
static int findLongestSub(String bin)
{
int n = bin.Length, i;
// To store sum.
int sum = 0;
// To store first occurrence of each
// sum value.
Dictionary<int,
int> prevSum = new Dictionary<int,
int>();
// To store maximum length.
int maxlen = 0;
// To store current substring length.
int currlen;
for (i = 0; i < n; i++)
{
// Add 1 if current character is 1
// else subtract 1.
if (bin[i] == '1')
sum++;
else
sum--;
// If sum is positive, then maximum
// length substring is bin[0..i]
if (sum > 0)
{
maxlen = i + 1;
}
// If sum is negative, then maximum
// length substring is bin[j+1..i], where
// sum of substring bin[0..j] is sum-1.
else if (sum <= 0)
{
if (prevSum.ContainsKey(sum - 1))
{
currlen = i - (prevSum[sum - 1] == 0 ? 1 :
prevSum[sum - 1]);
maxlen = Math.Max(maxlen, currlen);
}
}
// Make entry for this sum value in hash
// table if this value is not present.
if (!prevSum.ContainsKey(sum))
prevSum.Add(sum, i);
}
return maxlen;
}
// Driver code
public static void Main(String[] args)
{
String bin = "1010";
Console.WriteLine(findLongestSub(bin));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find largest substring
// having count of 1s more than count
// count of 0s.
// Function to find longest substring
// having count of 1s more than count
// of 0s.
function findLongestSub(bin)
{
let n = bin.length, i;
// To store sum.
let sum = 0;
// To store first occurrence of each
// sum value.
let prevSum = new Map();
// To store maximum length.
let maxlen = 0;
// To store current substring length.
let currlen;
for (i = 0; i < n; i++)
{
// Add 1 if current character is 1
// else subtract 1.
if (bin[i] == '1')
sum++;
else
sum--;
// If sum is positive, then maximum
// length substring is bin[0..i]
if (sum > 0)
{
maxlen = i + 1;
}
// If sum is negative, then maximum
// length substring is bin[j+1..i], where
// sum of substring bin[0..j] is sum-1.
else if (sum <= 0)
{
if (prevSum.has(sum - 1))
{
currlen = i - (prevSum.get(sum - 1) == null ? 1 :
prevSum.get(sum - 1));
maxlen = Math.max(maxlen, currlen);
}
}
// Make entry for this sum value in hash
// table if this value is not present.
if (!prevSum.has(sum))
prevSum.set(sum, i);
}
return maxlen;
}
// Driver code
let bin = "1010";
document.write(findLongestSub(bin));
// This code is contributed by rag2127
</script>
Producción:
3
Complejidad temporal: O(n)
Espacio auxiliar: O(n)