Minimice el reemplazo de bits para que el recuento de 01 substring sea igual a 10 substring

Dada una string binaria str . La tarea es minimizar el número de reemplazos de ‘0’ por ‘1’ o ‘1’ por ‘0’ para equilibrar la string binaria. Se dice que una string binaria está balanceada: “si el número de substring “01” = número de substring “10””.

Ejemplos:

Entrada: str = “101010” 
Salida: 1
Explicación: “01” = 2 y “10” = 3. Así que cambia el último carácter a ‘1’. La string modificada será «101011» o «001010».

Entrada: str = “0000100” // balanceado , “01” = 1 & “10” = 1
Salida: 0
Explicación: La string ya está balanceada.

Enfoque: se puede notar que «la string binaria balanceada siempre tendrá su primer carácter igual al último carácter de la string».
Solo se requiere un paso para equilibrarlo, es decir s.back() = s.front(). Ver la prueba proporcionada a continuación

Prueba:

El enfoque anterior se puede probar utilizando el Principio de inducción matemática.
NOTA: En la siguiente prueba, se consideran todos los casos en los que el primer carácter es igual al último carácter.

for n = 0 —> string vacía “” // cuenta de “10” = 0 & cuenta de “01” = 0
for n = 1 —> “0” o “1” // cuenta de “10” = 0 & recuento de “01” = 0  
para n = 2 —> “00” o “11” // recuento de “10” = 0 & recuento de “01” = 0
para n = 3 

—> “000” // cuenta de “10” = 0 y cuenta de “01” = 0
o “111” // cuenta de “10” = 0 y cuenta de “01” = 0
o “010” // cuenta de «10» = 1 y cuenta de «01» = 1
o «101» // cuenta de «10» = 1 y cuenta de «01» = 1

Por lo tanto, por el principio de inducción matemática, será cierto para todo n , donde n es un número natural .

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

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the minimum
// number of replacements
int minimizeReplacements(string str)
{
    unordered_map<string, int> count;
    string temp;
     
    // Loop to count the minimum number
    // of replacements required
    for (int i = 0; i <
        str.length() - 1; i++) {
        temp = str.substr(i, 2);
        count[temp]++;
    }
 
    return abs(count["10"] - count["01"]);
}
 
// Driver code
int main()
{
    // Given string
    string str = "101010";
    cout << minimizeReplacements(str) << endl;
    return 0;
}

// Java code to implement above approach
import java.util.HashMap;
 
class GFG{
 
// Function to count the minimum
// number of replacements
static int minimizeReplacements(String str)
{
    HashMap<String,
            Integer> count = new HashMap<String,
                                         Integer>();
    String temp;
 
    // Loop to count the minimum number
    // of replacements required
    for(int i = 0; i < str.length() - 1; i++)
    {
        temp = str.substring(i, i + 2);
        if (count.containsKey(temp))
            count.put(temp, count.get(temp) + 1);
        else
            count.put(temp, 1);
    }
    return Math.abs(count.get("10") - count.get("01"));
}
 
// Driver code
public static void main(String args[])
{
     
    // Given string
    String str = "101010";
    System.out.print(minimizeReplacements(str));
}
}
 
// This code is contributed by gfgking

# Python code for the above approach
 
# Function to count the minimum
# number of replacements
def minimizeReplacements(str):
    count = {}
    temp = ""
 
   # Loop to count the minimum number
   # of replacements required
    for i in range(0, len(str)-1):
        temp = str[i: i+2]
        if temp in count:
            count[temp] = count[temp] + 1
        else:
            count[temp] = 1
    return abs(count["10"] - count["01"])
 
    # Driver code
 
    # Given string
str = "101010"
print(minimizeReplacements(str))
 
# This code is contributed by Potta Lokesh

// C# code to implement above approach
using System;
using System.Collections.Generic;
class GFG
{
   
    // Function to count the minimum
    // number of replacements
    static int minimizeReplacements(string str)
    {
        Dictionary<string, int> count
            = new Dictionary<string, int>();
        string temp;
 
        // Loop to count the minimum number
        // of replacements required
        for (int i = 0; i < str.Length - 1; i++) {
            temp = str.Substring(i, 2);
            if (count.ContainsKey(temp))
                count[temp]++;
            else
                count[temp] = 1;
        }
 
        return Math.Abs(count["10"] - count["01"]);
    }
 
    // Driver code
    public static void Main()
    {
        // Given string
        string str = "101010";
        Console.WriteLine(minimizeReplacements(str));
    }
}
 
// This code is contributed by ukasp.

<script>
    // JavaScript code to implement above approach
 
    // Function to count the minimum
    // number of replacements
    const minimizeReplacements = (str) => {
        count = {};
        let temp = "";
 
        // Loop to count the minimum number
        // of replacements required
        for (let i = 0; i <
            str.length - 1; i++) {
            temp = str.substring(i, i + 2);
            if (temp in count) count[temp]++;
            else count[temp] = 1;
        }
 
        return Math.abs(count["10"] - count["01"]);
    }
 
    // Driver code
 
    // Given string
    let str = "101010";
    document.write(minimizeReplacements(str));
 
    //  This code is contributed by rakeshsahni
 
</script>

1

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