Minimice el volteo de bits en una string binaria dada para hacer que el recuento de 10 sea igual a 01

Dada la string binaria str , la tarea es elegir cualquier índice y cambiarlo a 0 o 1 , y hacerlo en pasos mínimos de modo que el recuento de la substring 01 sea igual a 10 .

Ejemplos:

Entrada: str = “01101”
Salida: 01100
Explicación: 01 como substring se repite 2 veces en una string, 10 como substring se repite 1 vez en una string. Entonces, cambie el último carácter 1 a 0, luego la cuenta de 01 y 10 es 1 e igual

Entrada: str = “01101010”
Salida: 01101010

Enfoque: si podemos observar que si el primer y el último carácter de la string son iguales, entonces la cuenta de «01» es igual a 1 porque, por inducción, siempre hay un carácter presente en el medio de la string, entonces podemos dividir una string en dos partes s[1….i], [i…n] entonces AB(s) = BA(s) .

• Si el primer y el último carácter no son iguales, cambie el primer carácter por el último carácter.
• Después de realizar los pasos anteriores, imprima el valor de str como respuesta.

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 make the count equal
string MakeEqual(string str)
{
 
    // Take first and last char of string
    char FirstChar = str[0];
    char LastChar = str[str.size() - 1];
 
    // Compare both the char
    if (FirstChar != LastChar) {
 
        // Copy lastchar inplace of
        // firstchar or viceversa
        str[0] = LastChar;
    }
 
    // If above condition is not true so
    // string remain unchanged
    // Return string
    return str;
}
 
// Driver Code
int main()
{
 
    string str = "0110101";
    string ans = MakeEqual(str);
    cout << ans;
    return 0;
}

// Java program for the above approach
class GFG
{
   
  // Function to make the count equal
  static String MakeEqual(String str) {
 
    // Take first and last char of String
    char FirstChar = str.charAt(0);
    char LastChar = str.charAt(str.length() - 1);
 
    // Compare both the char
    if (FirstChar != LastChar) {
 
      // Copy lastchar inplace of
      // firstchar or viceversa
      str = str.substring(1, str.length());
      str = LastChar + str;
 
    }
 
    // If above condition is not true so
    // String remain unchanged
    // Return String
    return str;
  }
 
  // Driver Code
  public static void main(String args[]) {
 
    String str = "0110101";
    String ans = MakeEqual(str);
    System.out.println(ans);
  }
}
 
// This code is contributed by saurabh_jaiswal.

# python3 program for the above approach
 
# Function to make the count equal
def MakeEqual(str):
 
    # Take first and last char of string
    FirstChar = str[0]
    LastChar = str[-1]
 
    # Compare both the char
    if (FirstChar != LastChar):
 
        # Copy lastchar inplace of
        # firstchar or viceversa
        str[0] = LastChar
 
    # If above condition is not true so
    # string remain unchanged
    # Return string
    return ''.join(str)
 
# Driver Code
if __name__ == "__main__":
 
    str = "0110101"
    ans = MakeEqual(list(str))
    print(ans)
 
    # This code is contributed by rakeshsahni

// C# program for the above approach
using System;
 
public class GFG
{
   
  // Function to make the count equal
  static String MakeEqual(String str) {
 
    // Take first and last char of String
    char FirstChar = str[0];
    char LastChar = str[str.Length - 1];
 
    // Compare both the char
    if (FirstChar != LastChar) {
 
      // Copy lastchar inplace of
      // firstchar or viceversa
      str = str.Substring(1, str.Length - 1);
      str = LastChar + str;
 
    }
 
    // If above condition is not true so
    // String remain unchanged
    // Return String
    return str;
  }
 
  // Driver Code
  public static void Main(String []args) {
 
    String str = "0110101";
    String ans = MakeEqual(str);
    Console.WriteLine(ans);
  }
}
 
// This code is contributed by shikhasingrajput

<script>
    // JavaScript code for the above approach
 
    // Function to make the count equal
    function MakeEqual(str)
    {
 
        // Take first and last char of string
        str = str.split('')
        let FirstChar = str[0];
        let LastChar = str[str.length - 1];
 
        // Compare both the char
        if (FirstChar != LastChar)
        {
 
            // Copy lastchar inplace of
            // firstchar or viceversa
            str[0] = LastChar;
        }
 
        // If above condition is not true so
        // string remain unchanged
        // Return string
        return str.join('');
    }
 
    // Driver Code
    let str = "0110101";
    let ans = MakeEqual(str);
    document.write(ans);
 
     // This code is contributed by Potta Lokesh
</script>

1110101

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)