Número mínimo de reemplazo hecho de la substring «01» con «110» para eliminarla por completo

Dada una string binaria S , la tarea es encontrar el número mínimo de reemplazos repetitivos de la substring «01» a la string «110» de modo que no exista ninguna substring «01» en la string dada S .

Ejemplos:

Entrada: S = “01”
Salida: 1
Explicación:
A continuación se muestran las operaciones realizadas:
Operación 1: Elegir la substring (0, 1) en la string “01” y reemplazarla con “110” modifica la string dada a “110”.
Después de las operaciones anteriores, la string S(= “110”) no contiene ninguna substring como “01”. Por lo tanto, el número total de operaciones requeridas es 1.

Entrada: S = “001”
Salida: 3
Explicación:
A continuación se muestran las operaciones realizadas:
Operación 1: Elegir la substring (1, 2) en la string “001” y reemplazarla con “110” modifica la string dada a “0110”.
Operación 2: Elegir la substring (0, 1) en la string «0110» y reemplazarla con «110» modifica la string dada a «11010».
Operación 3: Elegir la substring (2, 3) en la string «11010» y reemplazarla con «110» modifica la string dada a «111100».
Después de las operaciones anteriores, la string S(= “111100”) no contiene ninguna substring como “01”. Por lo tanto, el número total de operaciones requeridas es 3.

Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso . La operación es cada vez que se encuentra una substring «01» , se reemplaza con «110» y ahora el número ‘1’ está presente en el lado derecho de este ‘0’ forma la substring «01» que participa en el cambio de la string a “110” . Por lo tanto, la idea es recorrer la string desde el final y cada vez que aparezca ‘0’ , realizar la operación dada hasta el número de 1 presente en el lado derecho. Siga los pasos a continuación para resolver el problema:

• Inicialice dos variables, digamos ans y cntOne , ambas como 0 para almacenar el número mínimo de operaciones realizadas y cuente los 1 consecutivos desde el final durante el recorrido.
• Atraviese la string dada S desde el final y realice los siguientes pasos:
  • Si el carácter actual es 0 , entonces incremente el ans por el número de 1s consecutivos obtenidos hasta ahora y dos veces el valor del conteo de 1s consecutivos .
  • De lo contrario, incremente el valor de cntOne en 1 .
• Después de completar los pasos anteriores, imprima el valor de ans como el número mínimo de operaciones.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find the minimum number
// of replacement of "01" with "110"
// s.t. S doesn't contain substring "10"
void minimumOperations(string S, int N)
{
    // Stores the number of operations
    // performed
    int ans = 0;
 
    // Stores the resultant count
    // of substrings
    int cntOne = 0;
 
    // Traverse the string S from end
    for (int i = N - 1; i >= 0; i--) {
 
        // If the current character
        // is 0
        if (S[i] == '0') {
            ans += cntOne;
            cntOne *= 2;
        }
 
        // If the current character
        // is 1
        else
            cntOne++;
    }
 
    // Print the result
    cout << ans;
}
 
// Driver Code
int main()
{
    string S = "001";
    int N = S.length();
    minimumOperations(S, N);
 
    return 0;
}

// Java program for the above approach
 
import java.io.*;
 
class GFG {
    // Function to find the minimum number
    // of replacement of "01" with "110"
    // s.t. S doesn't contain substring "10"
    public static void minimumOperations(String S, int N)
    {
        // Stores the number of operations
        // performed
        int ans = 0;
 
        // Stores the resultant count
        // of substrings
        int cntOne = 0;
 
        // Traverse the string S from end
        for (int i = N - 1; i >= 0; i--) {
 
            // If the current character
            // is 0
            if (S.charAt(i) == '0') {
                ans += cntOne;
                cntOne *= 2;
            }
 
            // If the current character
            // is 1
            else
                cntOne++;
        }
 
        // Print the result
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String S = "001";
        int N = S.length();
        minimumOperations(S, N);
    }
}
 
  // This code is contributed by Potta Lokesh

# Python3 program for the above approach
 
# Function to find the minimum number
# of replacement of "01" with "110"
# s.t. S doesn't contain substring "10"
def minimumOperations(S, N):
     
    # Stores the number of operations
    # performed
    ans = 0
 
    # Stores the resultant count
    # of substrings
    cntOne = 0
 
    # Traverse the string S from end
    i = N - 1
     
    while(i >= 0):
         
        # If the current character
        # is 0
        if (S[i] == '0'):
            ans += cntOne
            cntOne *= 2
 
        # If the current character
        # is 1
        else:
            cntOne += 1
             
        i -= 1
 
    # Print the result
    print(ans)
 
# Driver Code
if __name__ == '__main__':
     
    S = "001"
    N = len(S)
     
    minimumOperations(S, N)
 
# This code is contributed by ipg2016107

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the minimum number
// of replacement of "01" with "110"
// s.t. S doesn't contain substring "10"
public static void minimumOperations(string S, int N)
{
     
    // Stores the number of operations
    // performed
    int ans = 0;
 
    // Stores the resultant count
    // of substrings
    int cntOne = 0;
 
    // Traverse the string S from end
    for(int i = N - 1; i >= 0; i--)
    {
         
        // If the current character
        // is 0
        if (S[i] == '0')
        {
            ans += cntOne;
            cntOne *= 2;
        }
 
        // If the current character
        // is 1
        else
            cntOne++;
    }
 
    // Print the result
    Console.WriteLine(ans);
}
 
// Driver code
static void Main()
{
    string S = "001";
    int N = S.Length;
     
    minimumOperations(S, N);
}
}
 
// This code is contributed by abhinavjain194

<script>
       // JavaScript program for the above approach
 
       // Function to find the minimum number
       // of replacement of "01" with "110"
       // s.t. S doesn't contain substring "10"
       function minimumOperations(S, N)
       {
        
           // Stores the number of operations
           // performed
           let ans = 0;
 
           // Stores the resultant count
           // of substrings
           let cntOne = 0;
 
           // Traverse the string S from end
           for (let i = N - 1; i >= 0; i--) {
 
               // If the current character
               // is 0
               if (S[i] == '0') {
                   ans += cntOne;
                   cntOne *= 2;
               }
 
               // If the current character
               // is 1
               else
                   cntOne++;
           }
 
           // Print the result
           document.write(ans);
       }
 
       // Driver Code
 
       let S = "001";
       let N = S.length;
       minimumOperations(S, N);
 
 // This code is contributed by Potta Lokesh
   </script>

3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)