Dada la string binaria str , la tarea es maximizar el recuento de 0 en la substring izquierda y 1 en la substring derecha dividiendo la string binaria dada en cualquier índice. Imprime la suma de dichos 0 y 1 al final.
Ejemplos:
Entrada: str = «0011110011»
Salida: 8
Explicación:
si una string se divide en el índice 2, entonces la substring izquierda = «00» y la substring derecha = «11110011».
Por lo tanto, la suma de la cuenta de 0 en la substring izquierda y 1 en la substring derecha es 2 + 6 = 8.Entrada: str = “0001101111011”
Salida: 11
Explicación:
si la string se divide en el índice 3, entonces la substring izquierda es “000” y la substring derecha es “1101111011”.
Por lo tanto, la suma de la cuenta de 0 en la substring izquierda y 1 en la substring derecha es 3 + 8 = 11.
Acercarse:
- Cuente el número de unos en la string binaria dada str (digamos totalOnes ).
- Recorre la string dada y mantén los conteos de 0s (digamos cero ) y 1s (digamos uno ).
- Durante el recorrido de la string, actualice la suma máxima como:
maxSum = max(maxSum, cero + (totalOnes – uno))
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to maximize the sum of the count
// of zeros and ones in the left and right
// substring
int maxSum(string& str)
{
int maximumSum = 0;
// To store the total ones
int totalOnes;
// Count the total numbers of ones
// in string str
totalOnes = count(str.begin(),
str.end(), '1');
// To store the count of zeros and
// ones while traversing string
int zero = 0, ones = 0;
// Iterate the given string and
// update the maximum sum
for (int i = 0; str[i]; i++) {
if (str[i] == '0') {
zero++;
}
else {
ones++;
}
// Update the maximum Sum
maximumSum
= max(
maximumSum,
zero + (totalOnes - ones));
}
return maximumSum;
}
// Driver Code
int main()
{
// Given binary string
string str = "011101";
// Function call
cout << maxSum(str);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to maximize the sum
// of the count of zeros and ones
// in the left and right substring
static int maxSum(String str)
{
int maximumSum = 0;
// To store the total ones
int totalOnes = 0;
// Count the total numbers of ones
// in string str
for(int i = 0; i < str.length(); i++)
{
if (str.charAt(i) == '1')
{
totalOnes++;
}
}
// To store the count of zeros and
// ones while traversing string
int zero = 0, ones = 0;
// Iterate the given string and
// update the maximum sum
for(int i = 0; i < str.length(); i++)
{
if (str.charAt(i) == '0')
{
zero++;
}
else
{
ones++;
}
// Update the maximum Sum
maximumSum = Math.max(maximumSum,
zero + (totalOnes - ones));
}
return maximumSum;
}
// Driver Code
public static void main(String args[])
{
// Given binary string
String str = "011101";
// Function call
System.out.println(maxSum(str));
}
}
// This code is contributed by rutvik_56
Python3
# Python3 program for the above approach # Function to maximize the sum of the count # of zeros and ones in the left and right # substring def maxSum(str): maximumSum = 0 # To store the total ones # Count the total numbers of ones # in str totalOnes = 0 for i in str: if i == '1': totalOnes += 1 # To store the count of zeros and # ones while traversing string zero = 0 ones = 0 # Iterate the given and # update the maximum sum i = 0 while i < len(str): if (str[i] == '0'): zero += 1 else: ones += 1 # Update the maximum Sum maximumSum= max(maximumSum,zero + (totalOnes - ones)) i += 1 return maximumSum # Driver Code if __name__ == '__main__': # Given binary string str = "011101" # Function call print(maxSum(str)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to maximize the sum
// of the count of zeros and ones
// in the left and right substring
static int maxSum(string str)
{
int maximumSum = 0;
// To store the total ones
int totalOnes = 0;
// Count the total numbers of ones
// in string str
for(int i = 0; i < str.Length; i++)
{
if (str[i] == '1')
{
totalOnes++;
}
}
// To store the count of zeros and
// ones while traversing string
int zero = 0, ones = 0;
// Iterate the given string and
// update the maximum sum
for(int i = 0; i < str.Length; i++)
{
if (str[i] == '0')
{
zero++;
}
else
{
ones++;
}
// Update the maximum Sum
maximumSum = Math.Max(maximumSum, zero +
(totalOnes -
ones));
}
return maximumSum;
}
// Driver Code
public static void Main(string []args)
{
// Given binary string
string str = "011101";
// Function call
Console.Write(maxSum(str));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program for the above approach
// Function to maximize the sum of the count
// of zeros and ones in the left and right
// substring
function maxSum(str)
{
var maximumSum = 0;
// To store the total ones
var totalOnes = 0;
// Count the total numbers of ones
// in string str
str.split('').forEach(c => {
if(c == '1')
totalOnes++;
});
// To store the count of zeros and
// ones while traversing string
var zero = 0, ones = 0;
// Iterate the given string and
// update the maximum sum
for (var i = 0; str[i]; i++) {
if (str[i] == '0') {
zero++;
}
else {
ones++;
}
// Update the maximum Sum
maximumSum
= Math.max(
maximumSum,
zero + (totalOnes - ones));
}
return maximumSum;
}
// Driver Code
// Given binary string
var str = "011101";
// Function call
document.write( maxSum(str));
</script>
Producción:
5
Complejidad de tiempo: O(N) , donde N es la longitud de la string.
Espacio Auxiliar: O(1)