Dada una string binaria de 0s y 1s . La tarea es encontrar la longitud de la substring que tiene una diferencia máxima entre el número de 0 y el número de 1 (número de 0 – número de 1 ). En el caso de todos los 1, imprima -1.
Ejemplos:
Input : S = "11000010001" Output : 6 From index 2 to index 9, there are 7 0s and 1 1s, so number of 0s - number of 1s is 6.
Input : S = "1111" Output : -1
Ahora, en cada índice i debemos tomar la decisión de tomarlo o saltearlo. Entonces, declare una array 2D de tamaño nx 2 , donde n es la longitud de la string binaria dada, digamos dp[n][2] .
dp[i][0] define the maximum value upto
index i, when we skip the i-th
index element.
dp[i][1] define the maximum value upto
index i after taking the i-th
index element.
Therefore, we can derive dp[i][] as:
dp[i][0] = max(dp[i+1][0], dp[i+1][1] + arr[i])
dp[i][1] = max(dp[i+1][1] + arr[i], 0)
Para todos, verificamos este caso explícitamente.
C++
// CPP Program to find the length of
// substring with maximum difference of
// zeroes and ones in binary string.
#include <bits/stdc++.h>
#define MAX 100
using namespace std;
// Return true if there all 1s
bool allones(string s, int n)
{
// Checking each index is 1 or not.
int co = 0;
for (int i = 0; i < s.size(); i++)
co += (s[i] == '1');
return (co == n);
}
// Find the length of substring with maximum
// difference of zeroes and ones in binary
// string
int findlength(int arr[], string s, int n, int ind, int st,
int dp[][3])
{
// If string is over.
if (ind >= n)
return 0;
// If the state is already calculated.
if (dp[ind][st] != -1)
return dp[ind][st];
if (st == 0)
return dp[ind][st]
= max(arr[ind]
+ findlength(arr, s, n, ind + 1, 1,
dp),
findlength(arr, s, n, ind + 1, 0, dp));
else
return dp[ind][st]
= max(arr[ind]
+ findlength(arr, s, n, ind + 1, 1,
dp),
0);
}
// Returns length of substring which is
// having maximum difference of number
// of 0s and number of 1s
int maxLen(string s, int n)
{
// If all 1s return -1.
if (allones(s, n))
return -1;
// Else find the length.
int arr[MAX] = { 0 };
for (int i = 0; i < n; i++)
arr[i] = (s[i] == '0' ? 1 : -1);
int dp[MAX][3];
memset(dp, -1, sizeof dp);
return findlength(arr, s, n, 0, 0, dp);
}
// Driven Program
int main()
{
string s = "11000010001";
int n = 11;
cout << maxLen(s, n) << endl;
return 0;
}
Java
// Java Program to find the length of
// substring with maximum difference of
// zeroes and ones in binary string.
import java.util.Arrays;
class GFG
{
static final int MAX=100;
// Return true if there all 1s
static boolean allones(String s, int n)
{
// Checking each index is 0 or not.
int co = 0;
for (int i = 0; i < s.length(); i++)
if(s.charAt(i) == '1')
co +=1;
return (co == n);
}
// Find the length of substring with maximum
// difference of zeroes and ones in binary
// string
static int findlength(int arr[], String s, int n,
int ind, int st, int dp[][])
{
// If string is over.
if (ind >= n)
return 0;
// If the state is already calculated.
if (dp[ind][st] != -1)
return dp[ind][st];
if (st == 0)
return dp[ind][st] = Math.max(arr[ind] +
findlength(arr, s, n,
ind + 1, 1, dp),
findlength(arr, s, n,
ind + 1, 0, dp));
else
return dp[ind][st] = Math.max(arr[ind] +
findlength(arr, s, n,
ind + 1, 1, dp), 0);
}
// Returns length of substring which is
// having maximum difference of number
// of 0s and number of 1s
static int maxLen(String s, int n)
{
// If all 1s return -1.
if (allones(s, n))
return -1;
// Else find the length.
int arr[] = new int[MAX];
for (int i = 0; i < n; i++)
arr[i] = (s.charAt(i) == '0' ? 1 : -1);
int dp[][] = new int[MAX][3];
for (int[] row : dp)
Arrays.fill(row, -1);
return findlength(arr, s, n, 0, 0, dp);
}
// Driver code
public static void main (String[] args)
{
String s = "11000010001";
int n = 11;
System.out.println(maxLen(s, n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python Program to find the length of # substring with maximum difference of # zeroes and ones in binary string. MAX = 100 # Return true if there all 1s def allones(s, n): # Checking each index # is 0 or not. co = 0 for i in s: co += 1 if i == '1' else 0 return co == n # Find the length of substring with # maximum difference of zeroes and # ones in binary string def findlength(arr, s, n, ind, st, dp): # If string is over if ind >= n: return 0 # If the state is already calculated. if dp[ind][st] != -1: return dp[ind][st] if not st: dp[ind][st] = max(arr[ind] + findlength(arr, s, n, ind + 1, 1, dp), (findlength(arr, s, n, ind + 1, 0, dp))) else: dp[ind][st] = max(arr[ind] + findlength(arr, s, n, ind + 1, 1, dp), 0) return dp[ind][st] # Returns length of substring which is # having maximum difference of number # of 0s and number of 1s def maxLen(s, n): # If all 1s return -1. if allones(s, n): return -1 # Else find the length. arr = [0] * MAX for i in range(n): arr[i] = 1 if s[i] == '0' else -1 dp = [[-1] * 3 for _ in range(MAX)] return findlength(arr, s, n, 0, 0, dp) # Driven Program s = "11000010001" n = 11 print(maxLen(s, n)) # This code is contributed by Ansu Kumari.
C#
// C# Program to find the length of
// substring with maximum difference of
// zeroes and ones in binary string.
using System;
class GFG
{
static int MAX = 100;
// Return true if there all 1s
public static bool allones(string s, int n)
{
// Checking each index is 0 or not.
int co = 0;
for (int i = 0; i < s.Length; i++)
co += (s[i] == '1' ? 1 : 0);
return (co == n);
}
// Find the length of substring with maximum
// difference of zeroes and ones in binary
// string
public static int findlength(int[] arr, string s,
int n, int ind, int st, int[,] dp)
{
// If string is over.
if (ind >= n)
return 0;
// If the state is already calculated.
if (dp[ind,st] != -1)
return dp[ind,st];
if (st == 0)
return dp[ind,st] = Math.Max(arr[ind] +
findlength(arr, s, n, ind + 1, 1, dp),
findlength(arr, s, n, ind + 1, 0, dp));
else
return dp[ind,st] = Math.Max(arr[ind] +
findlength(arr, s, n, ind + 1, 1, dp), 0);
}
// Returns length of substring which is
// having maximum difference of number
// of 0s and number of 1s
public static int maxLen(string s, int n)
{
// If all 1s return -1.
if (allones(s, n))
return -1;
// Else find the length.
int[] arr = new int[MAX];
for (int i = 0; i < n; i++)
arr[i] = (s[i] == '0' ? 1 : -1);
int[,] dp = new int[MAX,3];
for(int i = 0; i < MAX; i++)
for(int j = 0; j < 3; j++)
dp[i,j] = -1;
return findlength(arr, s, n, 0, 0, dp);
}
// Driven Program
static void Main()
{
string s = "11000010001";
int n = 11;
Console.Write(maxLen(s, n));
}
// This code is contributed by DrRoot_
}
Javascript
<script>
// Javascript Program to find the length of
// substring with maximum difference of
// zeroes and ones in binary string.
var MAX = 100;
// Return true if there all 1s
function allones( s, n)
{
// Checking each index is 0 or not.
var co = 0;
for (var i = 0; i < s.length; i++)
co += (s[i] == '1');
return (co == n);
}
// Find the length of substring with maximum
// difference of zeroes and ones in binary
// string
function findlength(arr, s, n, ind, st, dp)
{
// If string is over.
if (ind >= n)
return 0;
// If the state is already calculated.
if (dp[ind][st] != -1)
return dp[ind][st];
if (st == 0)
return dp[ind][st] = Math.max(arr[ind] +
findlength(arr, s, n, ind + 1, 1, dp),
findlength(arr, s, n, ind + 1, 0, dp));
else
return dp[ind][st] = Math.max(arr[ind] +
findlength(arr, s, n, ind + 1, 1, dp), 0);
}
// Returns length of substring which is
// having maximum difference of number
// of 0s and number of 1s
function maxLen( s, n)
{
// If all 1s return -1.
if (allones(s, n))
return -1;
// Else find the length.
var arr = Array(MAX).fill(0);
for (var i = 0; i < n; i++)
arr[i] = (s[i] == '0' ? 1 : -1);
var dp = Array.from(Array(MAX), ()=> Array(3).fill(-1));
return findlength(arr, s, n, 0, 0, dp);
}
// Driven Program
var s = "11000010001";
var n = 11;
document.write( maxLen(s, n));
</script>
Producción
6
Complejidad de tiempo: O(2*len(s)),
Espacio auxiliar: O(len(s))
Diferencia máxima de ceros y unos en string binaria | Conjunto 2 (tiempo O(n))