Dada una string binaria de 0s y 1s. La tarea es encontrar la diferencia máxima entre el número de 0 y el número de 1 en cualquier substring de la string binaria dada. Eso es maximizar (número de 0 – número de 1) para cualquier substring en la string binaria dada.
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
Hemos discutido el enfoque de programación dinámica en la siguiente publicación:
Diferencia máxima de ceros y unos en string binaria | conjunto 1 .
En la publicación vimos un método eficiente que funciona en tiempo O(n) y en espacio adicional O(1). Idea detrás de eso si convertimos todos los ceros en 1 y todos los unos en -1. Ahora nuestro problema se reduce a encontrar la suma máxima de sub_array usando el algoritmo de Kadane .
Input : S = "11000010001" After converting '0' into 1 and '1' into -1 our S Look Like S = -1 -1 1 1 1 1 -1 1 1 1 -1 Now we have to find out Maximum Sum sub_array that is : 6 is that case Output : 6
A continuación se muestra la implementación de la idea anterior.
C++
// CPP Program to find the length of // substring with maximum difference of // zeros and ones in binary string. #include <iostream> using namespace std; // Returns the length of substring with // maximum difference of zeroes and ones // in binary string int findLength(string str, int n) { int current_sum = 0; int max_sum = 0; // traverse a binary string from left // to right for (int i = 0; i < n; i++) { // add current value to the current_sum // according to the Character // if it's '0' add 1 else -1 current_sum += (str[i] == '0' ? 1 : -1); if (current_sum < 0) current_sum = 0; // update maximum sum max_sum = max(current_sum, max_sum); } // return -1 if string does not contain // any zero that means all ones // otherwise max_sum return max_sum == 0 ? -1 : max_sum; } // Driven Program int main() { string s = "11000010001"; int n = 11; cout << findLength(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.*; import java.lang.*; import java.io.*; class GFG { // Find the length of substring with maximum // difference of zeros and ones in binary // string public static int findLength(String str, int n) { int current_sum = 0; int max_sum = 0; // traverse a binary string from left to right for (int i = 0; i < n; i++) { // add current value to the current_sum // according to the Character // if it's '0' add 1 else -1 current_sum += (str.charAt(i) == '0' ? 1 : -1); if (current_sum < 0) current_sum = 0; // update maximum sum max_sum = Math.max(current_sum, max_sum); } // return -1 if string does not contain any zero // that means string contains all ones otherwise max_sum return max_sum == 0 ? -1 : max_sum; } public static void main(String[] args) { String str = "11000010001"; int n = str.length(); System.out.println(findLength(str, n)); } }
Python3
# Python Program to find the length of # substring with maximum difference of # zeros and ones in binary string. # Returns the length of substring with # maximum difference of zeroes and ones # in binary string def findLength(string, n): current_sum = 0 max_sum = 0 # traverse a binary string from left # to right for i in range(n): # add current value to the current_sum # according to the Character # if it's '0' add 1 else -1 current_sum += (1 if string[i] == '0' else -1) if current_sum < 0: current_sum = 0 # update maximum sum max_sum = max(current_sum, max_sum) # return -1 if string does not contain # any zero that means all ones # otherwise max_sum return max_sum if max_sum else 0 # Driven Program s = "11000010001" n = 11 print(findLength(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 { // Find the length of substring with // maximum difference of zeros and // ones in binary string public static int findLength(string str, int n) { int current_sum = 0; int max_sum = 0; // traverse a binary string // from left to right for (int i = 0; i < n; i++) { // add current value to the current_sum // according to the Character // if it's '0' add 1 else -1 current_sum += (str[i] == '0' ? 1 : -1); if (current_sum < 0) { current_sum = 0; } // update maximum sum max_sum = Math.Max(current_sum, max_sum); } // return -1 if string does not contain // any zero that means string contains // all ones otherwise max_sum return max_sum == 0 ? -1 : max_sum; } // Driver Code public static void Main(string[] args) { string str = "11000010001"; int n = str.Length; Console.WriteLine(findLength(str, n)); } } // This code is contributed by Shrikant13
PHP
<?php // PHP Program to find the length of // substring with maximum difference of // zeros and ones in binary string. // Returns the length of substring with // maximum difference of zeroes and ones // in binary string function findLength($str, $n) { $current_sum = 0; $max_sum = 0; // traverse a binary string // from left to right for ($i = 0; $i < $n; $i++) { // add current value to the current_sum // according to the Character // if it's '0' add 1 else -1 $current_sum += ($str[$i] == '0' ? 1 : -1); if ($current_sum < 0) $current_sum = 0; // update maximum sum $max_sum = max($current_sum, $max_sum); } // return -1 if string does not contain // any zero that means all ones // otherwise max_sum return $max_sum == 0 ? -1 : $max_sum; } // Driver Code $s = "11000010001"; $n = 11; echo findLength($s, $n),"\n"; // This code is contributed by aj_36 ?>
Javascript
<script> // JavaScript program to find the length of // substring with maximum difference of // zeroes and ones in binary string. // Find the length of substring with // maximum difference of zeros and // ones in binary string function findLength(str, n) { let current_sum = 0; let max_sum = 0; // traverse a binary string // from left to right for (let i = 0; i < n; i++) { // add current value to the current_sum // according to the Character // if it's '0' add 1 else -1 current_sum += (str[i] == '0' ? 1 : -1); if (current_sum < 0) { current_sum = 0; } // update maximum sum max_sum = Math.max(current_sum, max_sum); } // return -1 if string does not contain // any zero that means string contains // all ones otherwise max_sum return max_sum == 0 ? -1 : max_sum; } // Driver Code let str = "11000010001"; let n = str.length; document.write(findLength(str, n)); // This code is contributed by chinmoy1997pal. </script>
Producción:
6
Complejidad de tiempo: O(n)
Complejidad de espacio: O(n), ya que la string se copia cuando la pasamos a una función.
Publicación traducida automáticamente
Artículo escrito por Nishant_Singh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA