Número mínimo de reemplazos para hacer que la string binaria se alterné | conjunto 2

Dada una string binaria str , la tarea es encontrar el número mínimo de caracteres en la string que deben reemplazarse para que la string sea alterna (es decir, de la forma 01010101… o 10101010… ).
Ejemplos: 
 

Entrada: str = “1100” 
Salida: 2 
Reemplace el 2 ^° carácter con ‘0’ y el 3 ^° carácter con ‘1’
Entrada: str = “1010” 
Salida: 0 
La string ya está alternando. 
 

Hemos discutido un enfoque en Número de vueltas para alternar strings binarias . En este post se discute un mejor enfoque.
Enfoque: para la string str , puede haber dos soluciones posibles. La string resultante puede ser 
 

1. 010101… o
2. 101010…

Para encontrar los reemplazos mínimos, cuente el número de reemplazos para convertir la string en tipo 1 y guárdelo en el conteo , luego el reemplazo mínimo será min (recuento, len – conteo) donde len es la longitud de la string. len – count es el número de reemplazos para convertir la string en tipo 2.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum number of
// characters of the given binary string
// to be replaced to make the string alternating
int minReplacement(string s, int len)
{
    int ans = 0;
    for (int i = 0; i < len; i++) {
 
        // If there is 1 at even index positions
        if (i % 2 == 0 && s[i] == '1')
            ans++;
 
        // If there is 0 at odd index positions
        if (i % 2 == 1 && s[i] == '0')
            ans++;
    }
    return min(ans, len - ans);
}
 
// Driver code
int main()
{
    string s = "1100";
    int len = s.size();
    cout << minReplacement(s, len);
 
    return 0;
}

// Java implementation of the approach
class GFG {
 
    // Function to return the minimum number of
    // characters of the given binary string
    // to be replaced to make the string alternating
    static int minReplacement(String s, int len)
    {
        int ans = 0;
        for (int i = 0; i < len; i++) {
 
            // If there is 1 at even index positions
            if (i % 2 == 0 && s.charAt(i) == '1')
                ans++;
 
            // If there is 0 at odd index positions
            if (i % 2 == 1 && s.charAt(i) == '0')
                ans++;
        }
        return Math.min(ans, len - ans);
    }
 
    // Driver code
    public static void main(String args[])
    {
        String s = "1100";
        int len = s.length();
        System.out.print(minReplacement(s, len));
    }
}

# Python3 implementation of the approach.
 
# Function to return the minimum number of
# characters of the given binary string
# to be replaced to make the string alternating
def minReplacement(s, length):
 
    ans = 0
    for i in range(0, length):
 
        # If there is 1 at even index positions
        if i % 2 == 0 and s[i] == '1':
            ans += 1
 
        # If there is 0 at odd index positions
        if i % 2 == 1 and s[i] == '0':
            ans += 1
     
    return min(ans, length - ans)
 
# Driver code
if __name__ == "__main__":
 
    s = "1100"
    length = len(s)
    print(minReplacement(s, length))
         
# This code is contributed by Rituraj Jain

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Function to return the minimum number of
    // characters of the given binary string
    // to be replaced to make the string alternating
    static int minReplacement(String s, int len)
    {
        int ans = 0;
        for (int i = 0; i < len; i++)
        {
 
            // If there is 1 at even index positions
            if (i % 2 == 0 && s[i] == '1')
                ans++;
 
            // If there is 0 at odd index positions
            if (i % 2 == 1 && s[i] == '0')
                ans++;
        }
        return Math.Min(ans, len - ans);
    }
 
    // Driver code
    public static void Main(String []args)
    {
        String s = "1100";
        int len = s.Length;
        Console.Write(minReplacement(s, len));
    }
}
 
// This code contributed by Rajput-Ji

<?php
// PHP implementation of the approach
 
// Function to return the minimum number of
// characters of the given binary string
// to be replaced to make the string alternating
function minReplacement($s, $len)
{
    $ans = 0;
    for ($i = 0; $i < $len; $i++)
    {
 
        // If there is 1 at even index positions
        if ($i % 2 == 0 && $s[$i] == '1')
            $ans++;
 
        // If there is 0 at odd index positions
        if ($i % 2 == 1 && $s[$i] == '0')
            $ans++;
    }
    return min($ans, $len - $ans);
}
 
// Driver code
$s = "1100";
$len = strlen($s);
echo minReplacement($s, $len);
 
// This code is contributed by chandan_jnu
?>

<script>
 
 
// Javascript implementation of the approach
 
// Function to return the minimum number of
// characters of the given binary string
// to be replaced to make the string alternating
function minReplacement(s, len)
{
    var ans = 0;
    for (var i = 0; i < len; i++) {
 
        // If there is 1 at even index positions
        if (i % 2 == 0 && s[i] == '1')
            ans++;
 
        // If there is 0 at odd index positions
        if (i % 2 == 1 && s[i] == '0')
            ans++;
    }
    return Math.min(ans, len - ans);
}
 
// Driver code
var s = "1100";
var len = s.length;
document.write(minReplacement(s, len));
 
 
</script>

2

Complejidad de tiempo: O(len), donde len es la longitud de la string dada. Estamos atravesando hasta len.

Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.