Fractionner une chaîne binaire de sorte que le nombre de 0 et de 1 dans les sous-chaînes gauche et droite soit maximal

Afficher la discussion

Améliorer l’article

Enregistrer l’article

J’aime l’article

Afficher la discussion

Améliorer l’article

Enregistrer l’article

J’aime l’article

Étant donné un binaire chaîne de caractères, chaîne de longueur Nla tâche consiste à trouver la somme maximale du nombre de 0 à gauche sous-chaîne et compte de 1 sur la sous-chaîne de droite possible en divisant le chaîne binaire en deux sous-chaînes non vides.

Exemples:

Saisir: chaîne = “000111”
Production: 6
Explication:
Division de la chaîne binaire en “000” et “111”.
Nombre de 0 dans la sous-chaîne gauche de la chaîne = 3
Nombre de 1 dans la sous-chaîne droite de la chaîne = 3
Par conséquent, la somme du nombre de 0 dans la sous-chaîne gauche de la chaîne et du nombre de 1 dans la sous-chaîne droite de la chaîne = 3 + 3 = 6.

Saisir: S = “1111”
Production: 3
Explication:
Fractionnement de la chaîne binaire en “1” et “111”.
Nombre de 0 dans la sous-chaîne gauche de la chaîne = 0
Nombre de 1 dans la sous-chaîne droite de la chaîne = 3
Par conséquent, la somme du nombre de 0 dans la sous-chaîne gauche de la chaîne et du nombre de 1 dans la sous-chaîne droite de la chaîne = 0 + 3 = 3.

Approcher: Suivez les étapes ci-dessous pour résoudre le problème :

  1. Initialiser une variable, disons respour stocker la somme maximale du nombre de 0s dans la sous-chaîne gauche et nombre de 1s dans la sous-chaîne de droite.
  2. Initialiser une variable, disons cntOnepour stocker le nombre de 1s dans la chaîne binaire donnée.
  3. Traverser la chaîne binaire et pour chaque caractère, vérifiez s’il est ‘1’ ou non. S’il s’avère vrai, incrémentez la valeur de cntOne par 1.
  4. Initialiser deux variables, disons zéro et unepour stocker le nombre de 0s et compte de 1toujours jee indice.
  5. Traverser la chaîne binaire et mettre à jour la valeur de res = max(res, cntOne – un + zéro).
  6. Enfin, imprimez la valeur de res.

Voici la mise en œuvre de l’approche ci-dessus :

C++

#include <bits/stdc++.h>

using namespace std;

int maxSumbySplittingstring(string str, int N)

{

    

    

    int cntOne = 0;

    

    for (int i = 0; i < N; i++) {

        

        if (str[i] == '1') {

            

            cntOne++;

        }

    }

    

    int zero = 0;

    

    int one = 0;

    

    

    int res = 0;

    

    for (int i = 0; i < N - 1; i++) {

        

        

        if (str[i] == '0') {

            

            zero++;

        }

        

        else {

            

            one++;

        }

        

        res = max(res, zero + cntOne - one);

    }

    return res;

}

int main()

{

    string str = "00111";

    int N = str.length();

    cout << maxSumbySplittingstring(str, N);

    return 0;

}

Java

import java.util.*;

class GFG

{

  

  

  

  static int maxSumbySplittingString(String str, int N)

  {

    

    

    int cntOne = 0;

    

    for (int i = 0; i < N; i++)

    {

      

      if (str.charAt(i) == '1')

      {

        

        cntOne++;

      }

    }

    

    int zero = 0;

    

    int one = 0;

    

    

    int res = 0;

    

    for (int i = 0; i < N - 1; i++) {

      

      

      if (str.charAt(i) == '0') {

        

        zero++;

      }

      

      else {

        

        one++;

      }

      

      res = Math.max(res, zero + cntOne - one);

    }

    return res;

  }

  

  public static void main(String[] args)

  {

    String str = "00111";

    int N = str.length();

    System.out.print(maxSumbySplittingString(str, N));

  }

}

Python3

def maxSumbySplittingstring(str, N):

    

    

    cntOne = 0

    

    for i in range(N):

        

        if (str[i] == '1'):

            

            cntOne += 1

    

    zero = 0

    

    one = 0

    

    

    res = 0

    

    for i in range(N - 1):

        

        

        if (str[i] == '0'):

            

            zero += 1

        

        else:

            

            one += 1

        

        res = max(res, zero + cntOne - one)

    return res

if __name__ == '__main__':

    str = "00111"

    N = len(str)

    print (maxSumbySplittingstring(str, N))

    

C#

using System;

public class GFG

{

  

  

  

  static int maxSumbySplittingString(String str, int N)

  {

    

    

    int cntOne = 0;

    

    for (int i = 0; i < N; i++)

    {

      

      if (str[i] == '1')

      {

        

        cntOne++;

      }

    }

    

    int zero = 0;

    

    int one = 0;

    

    

    int res = 0;

    

    for (int i = 0; i < N - 1; i++) {

      

      

      if (str[i] == '0') {

        

        zero++;

      }

      

      else {

        

        one++;

      }

      

      res = Math.Max(res, zero + cntOne - one);

    }

    return res;

  }

  

  public static void Main(String[] args)

  {

    String str = "00111";

    int N = str.Length;

    Console.Write(maxSumbySplittingString(str, N));

  }

}

Javascript

<script>

function maxSumbySplittingstring(str, N)

{

    

    

    var cntOne = 0;

    

    for(var i = 0; i < N; i++) {

        

        if (str[i] == '1') {

            

            cntOne++;

        }

    }

    

    var zero = 0;

    

    var one = 0;

    

    

    var res = 0;

    

    for (var i = 0; i < N - 1; i++) {

        

        

        if (str[i] == '0') {

            

            zero++;

        }

        

        else {

            

            one++;

        }

        

        res = Math.max(res, zero + cntOne - one);

    }

    return res;

}

var str = "00111";

var N = str.length;

document.write( maxSumbySplittingstring(str, N));

</script>

Complexité temporelle : SUR)
Espace Auxiliaire : O(1)

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *