Dada una string binaria , str de longitud N , la tarea es encontrar la suma máxima del recuento de 0 en la substring izquierda y el recuento de 1 en la substring derecha posible al dividir la string binaria en dos substrings no vacías.
Ejemplos:
Entrada: str = “000111”
Salida: 6
Explicación:
Dividir la string binaria en “000” y “111”.
Cuenta de 0s en la substring izquierda de la string = 3
Cuenta de 1s en la substring derecha de la string = 3
Por lo tanto, la suma de la cuenta de 0s en la substring izquierda de la string y la cuenta de 1s en la substring derecha de la cuerda = 3 + 3 = 6.
Entrada: S = “1111”
Salida: 3
Explicación:
División de la string binaria en “1” y “111”.
Conteo de 0s en la substring izquierda de la string = 0
Conteo de 1s en la substring derecha de la string = 3
Por lo tanto, la suma del conteo de 0s en la substring izquierda de la string y el conteo de 1s en la substring derecha de la string = 0 + 3 = 3.
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos res , para almacenar la suma máxima de conteo de 0 s en la substring izquierda y conteo de 1 s en la substring derecha.
- Inicialice una variable, digamos cntOne , para almacenar el conteo de 1 s en la string binaria dada.
- Recorra la string binaria y para cada carácter, verifique si es ‘1’ o no. Si se determina que es cierto, incremente el valor de cntOne en 1 .
- Inicialice dos variables, digamos cero y uno , para almacenar el conteo de 0 s y el conteo de 1 s hasta el i -ésimo índice.
- Recorra la string binaria y actualice el valor de res = max(res, cntOne – one + zero) .
- Finalmente, imprima el valor de res .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum sum of count of
// 0s in the left substring and count of 1s in
// the right substring by splitting the string
int maxSumbySplittingstring(string str, int N)
{
// Stores count of 1s
// the in binary string
int cntOne = 0;
// Traverse the binary string
for (int i = 0; i < N; i++) {
// If current character is '1'
if (str[i] == '1') {
// Update cntOne
cntOne++;
}
}
// Stores count of 0s
int zero = 0;
// Stores count of 1s
int one = 0;
// Stores maximum sum of count of
// 0s and 1s by splitting the string
int res = 0;
// Traverse the binary string
for (int i = 0; i < N - 1; i++) {
// If current character
// is '0'
if (str[i] == '0') {
// Update zero
zero++;
}
// If current character is '1'
else {
// Update one
one++;
}
// Update res
res = max(res, zero + cntOne - one);
}
return res;
}
// Driver Code
int main()
{
string str = "00111";
int N = str.length();
cout << maxSumbySplittingstring(str, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
// Function to find the maximum sum of count of
// 0s in the left subString and count of 1s in
// the right subString by splitting the String
static int maxSumbySplittingString(String str, int N)
{
// Stores count of 1s
// the in binary String
int cntOne = 0;
// Traverse the binary String
for (int i = 0; i < N; i++)
{
// If current character is '1'
if (str.charAt(i) == '1')
{
// Update cntOne
cntOne++;
}
}
// Stores count of 0s
int zero = 0;
// Stores count of 1s
int one = 0;
// Stores maximum sum of count of
// 0s and 1s by splitting the String
int res = 0;
// Traverse the binary String
for (int i = 0; i < N - 1; i++) {
// If current character
// is '0'
if (str.charAt(i) == '0') {
// Update zero
zero++;
}
// If current character is '1'
else {
// Update one
one++;
}
// Update res
res = Math.max(res, zero + cntOne - one);
}
return res;
}
// Driver Code
public static void main(String[] args)
{
String str = "00111";
int N = str.length();
System.out.print(maxSumbySplittingString(str, N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach # Function to find the maximum sum of count of # 0s in the left suband count of 1s in # the right subby splitting the string def maxSumbySplittingstring(str, N): # Stores count of 1s # the in binary string cntOne = 0 # Traverse the binary string for i in range(N): # If current character is '1' if (str[i] == '1'): # Update cntOne cntOne += 1 # Stores count of 0s zero = 0 # Stores count of 1s one = 0 # Stores maximum sum of count of # 0s and 1s by splitting the string res = 0 # Traverse the binary string for i in range(N - 1): # If current character # is '0' if (str[i] == '0'): # Update zero zero += 1 # If current character is '1' else: # Update one one += 1 # Update res res = max(res, zero + cntOne - one) return res # Driver Code if __name__ == '__main__': str = "00111" N = len(str) print (maxSumbySplittingstring(str, N)) # This code is contributed by mohit kumar 29.
C#
// C# program to implement
// the above approach
using System;
public class GFG
{
// Function to find the maximum sum of count of
// 0s in the left subString and count of 1s in
// the right subString by splitting the String
static int maxSumbySplittingString(String str, int N)
{
// Stores count of 1s
// the in binary String
int cntOne = 0;
// Traverse the binary String
for (int i = 0; i < N; i++)
{
// If current character is '1'
if (str[i] == '1')
{
// Update cntOne
cntOne++;
}
}
// Stores count of 0s
int zero = 0;
// Stores count of 1s
int one = 0;
// Stores maximum sum of count of
// 0s and 1s by splitting the String
int res = 0;
// Traverse the binary String
for (int i = 0; i < N - 1; i++) {
// If current character
// is '0'
if (str[i] == '0') {
// Update zero
zero++;
}
// If current character is '1'
else {
// Update one
one++;
}
// Update res
res = Math.Max(res, zero + cntOne - one);
}
return res;
}
// Driver Code
public static void Main(String[] args)
{
String str = "00111";
int N = str.Length;
Console.Write(maxSumbySplittingString(str, N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the maximum sum of count of
// 0s in the left substring and count of 1s in
// the right substring by splitting the string
function maxSumbySplittingstring(str, N)
{
// Stores count of 1s
// the in binary string
var cntOne = 0;
// Traverse the binary string
for(var i = 0; i < N; i++) {
// If current character is '1'
if (str[i] == '1') {
// Update cntOne
cntOne++;
}
}
// Stores count of 0s
var zero = 0;
// Stores count of 1s
var one = 0;
// Stores maximum sum of count of
// 0s and 1s by splitting the string
var res = 0;
// Traverse the binary string
for (var i = 0; i < N - 1; i++) {
// If current character
// is '0'
if (str[i] == '0') {
// Update zero
zero++;
}
// If current character is '1'
else {
// Update one
one++;
}
// Update res
res = Math.max(res, zero + cntOne - one);
}
return res;
}
// Driver Code
var str = "00111";
var N = str.length;
document.write( maxSumbySplittingstring(str, N));
</script>
Producción:
5
Complejidad temporal: O(N)
Espacio auxiliar: O(1)