String binaria lexicográficamente más pequeña formada usando intercambios infinitos

Dada una string binaria s de longitud N, la tarea es encontrar la string lexicográficamente más pequeña utilizando un número infinito de intercambios entre 0 y 1 .

Ejemplos:

Entrada : s = “1001001”
Salida : 0000111
Explicación : la string lexicográficamente más pequeña de 1001001 es solo 0000111

Entrada : s = “0001”
Salida : 0001
Explicación : la string lexicográficamente más pequeña de 0001 es solo 0001

Entrada : s = “1”
Salida : 1
Explicación : Lexicográficamente, la string más pequeña de 1 es solo 1

Enfoque ingenuo: el enfoque más básico para resolver este problema se basa en la siguiente idea:

Dado que se nos permite hacer intercambios infinitos entre 0 y 1. Por lo tanto, al intercambiar, obtendremos una de esas combinaciones donde todos los 0 vendrán antes que todos los 1.

Como por definición, la string binaria lexicográficamente más pequeña debe tener solo 0 antes que solo 1, por lo tanto, la combinación anterior producirá la salida requerida.

Ahora, para encontrar dicha combinación, podemos intercambiar 0 y 1 uno por uno, hasta que obtengamos la combinación requerida donde todos los 0 están antes que todos los 1.

Complejidad de tiempo: O(N!), para encontrar todas esas combinaciones de strings binarias dadas
Espacio auxiliar: O(1)

Enfoque 2: El enfoque anterior se puede optimizar evitando la necesidad de encontrar todas las combinaciones, según la siguiente observación:

Dado que necesitamos encontrar una combinación en la que todos los 0 vengan antes que todos los 1, podemos ordenar la string binaria dada en su lugar, para obtener la string binaria lexicográficamente más pequeña requerida.

Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar aún más al evitar la necesidad de ordenar la string binaria dada por completo, según la siguiente idea:

En lugar de ordenar la string binaria dada, podemos simplemente encontrar el recuento de bits activados y desactivados (0 y 1) y formar un nuevo binario con el mismo recuento donde todos los 0 vienen antes que todos los 1.

Con base en la idea anterior, siga los pasos a continuación para implementar este enfoque:

• Cuente el número de 0 y 1 en una string binaria dada.
• Crear una nueva string vacía
• Inserte 0 en la string vacía igual a la cuenta de 0 en la string original.
• Luego agregue 1s en la nueva string igual al conteo de 1s en la string original.
• Devuelve la nueva string como la string binaria lexicográficamente más pequeña.

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

// C++ code to implement the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of 0s
int countOfXs(string s, char x)
{
    int n = s.length();
    int no_of_x = 0;
 
    for (int i = 0; i < n; i++) {
        // if character is 0
        // then increase the count of 0's
        if (s[i] == x)
            no_of_x++;
    }
 
    return no_of_x;
}
 
// Function to find the lexicographically
// smallest string using infinite swaps
string lexSmallestBinaryString(string s)
{
 
    // Variables to count no of 0 and no of 1
    int no_of_0 = countOfXs(s, '0');
    int no_of_1 = countOfXs(s, '1');
 
    // Create new string to store
    // the required string
    s = "";
 
    // Put all 0's first in resultant string
    for (int i = 0; i < no_of_0; i++) {
        // Make character equal to 0
        s += '0';
    }
 
    // Append all 1's in resultant string
    for (int i = 0; i < no_of_1; i++) {
        // Make character equal to 1
        s += '1';
    }
 
    // Return the resultant string
    return s;
}
 
// Driver code
int main()
{
    string s = "1111000011";
 
    cout << lexSmallestBinaryString(s);
 
    return 0;
}

// Java code to implement the approach
class GFG
{
 
  // Function to find the count of 0s
  static int countOfXs(String s, char x)
  {
    int n = s.length();
    int no_of_x = 0;
 
    for (int i = 0; i < n; i++)
    {
 
      // if character is 0
      // then increase the count of 0's
      if (s.charAt(i) == x)
        no_of_x++;
    }
 
    return no_of_x;
  }
 
  // Function to find the lexicographically
  // smallest string using infinite swaps
  static String lexSmallestBinaryString(String s)
  {
 
    // Variables to count no of 0 and no of 1
    int no_of_0 = countOfXs(s, '0');
    int no_of_1 = countOfXs(s, '1');
 
    // Create new string to store
    // the required string
    s = "";
 
    // Put all 0's first in resultant string
    for (int i = 0; i < no_of_0; i++)
    {
 
      // Make character equal to 0
      s += '0';
    }
 
    // Append all 1's in resultant string
    for (int i = 0; i < no_of_1; i++)
    {
 
      // Make character equal to 1
      s += '1';
    }
 
    // Return the resultant string
    return s;
  }
  public static void main(String[] args)
  {
 
    String s = "1111000011";
 
    System.out.println(lexSmallestBinaryString(s));
  }
}
 
// This code is contributed by phasing17.

# Python3 code for the above approach
 
# Function to find the count of 0s
def countOfXs(s, x):
    n = len(s)
    no_of_x = 0
 
    for i in range(n):
       
        # if character is 0
        # hen increase the count of 0's
        if s[i] == x:
            no_of_x += 1
     
    return no_of_x
 
# Function to find the lexicographically
# smallest string using infinite swaps
def lexSmallestBinaryString(s):
   
    # Variables to count no of 0 and no of 1
    no_of_0 = countOfXs(s, '0')
    no_of_1 = countOfXs(s, "1")
     
    # Create new string to store
    # the required string
    s = ""
     
    # Put all 0's first in resultant string
    for i in range(no_of_0):
       
        # Make character equal to 0
        s += "0"
         
    # Append all 1's in resultant string
    for i in range(no_of_1):
       
        # Make character equal to 1
        s += "1"
         
    # Return the resultant string
    return s
 
# Driver code
s = "1111000011"
  
# function call
print(lexSmallestBinaryString(s))
 
# This code is contributed by phasing17

// C# code to implement the above approach
using System;
class GFG {
 
    // Function to find the count of 0s
    static int countOfXs(string s, char x)
    {
        int n = s.Length;
        int no_of_x = 0;
 
        for (int i = 0; i < n; i++) {
            // if character is 0
            // then increase the count of 0's
            if (s[i] == x)
                no_of_x++;
        }
 
        return no_of_x;
    }
 
    // Function to find the lexicographically
    // smallest string using infinite swaps
    static string lexSmallestBinaryString(string s)
    {
 
        // Variables to count no of 0 and no of 1
        int no_of_0 = countOfXs(s, '0');
        int no_of_1 = countOfXs(s, '1');
 
        // Create new string to store
        // the required string
        s = "";
 
        // Put all 0's first in resultant string
        for (int i = 0; i < no_of_0; i++) {
            // Make character equal to 0
            s += '0';
        }
 
        // Append all 1's in resultant string
        for (int i = 0; i < no_of_1; i++) {
            // Make character equal to 1
            s += '1';
        }
 
        // Return the resultant string
        return s;
    }
 
    // Driver code
    public static void Main()
    {
        string s = "1111000011";
 
        Console.Write(lexSmallestBinaryString(s));
    }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to find the count of 0s
       function countOfXs(s, x) {
           let n = s.length;
           let no_of_x = 0;
 
           for (let i = 0; i < n; i++)
           {
            
               // if character is 0
               // then increase the count of 0's
               if (s[i] == x)
                   no_of_x++;
           }
 
           return no_of_x;
       }
 
       // Function to find the lexicographically
       // smallest string using infinite swaps
       function lexSmallestBinaryString(s) {
 
           // Variables to count no of 0 and no of 1
           let no_of_0 = countOfXs(s, '0');
           let no_of_1 = countOfXs(s, '1');
 
           // Create new string to store
           // the required string
           s = "";
 
           // Put all 0's first in resultant string
           for (let i = 0; i < no_of_0; i++) {
               // Make character equal to 0
               s += '0';
           }
 
           // Append all 1's in resultant string
           for (let i = 0; i < no_of_1; i++)
           {
            
               // Make character equal to 1
               s += '1';
           }
 
           // Return the resultant string
           return s;
       }
 
       // Driver code
       let s = "1111000011";
       document.write(lexSmallestBinaryString(s));
 
   // This code is contributed by Potta Lokesh
   </script>

0000111111

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