La string lexicográficamente más pequeña formada repetidamente eliminando el carácter de la substring 10

Dada una string binaria S de longitud N , la tarea es encontrar lexicográficamente la string más pequeña formada después de modificar la string seleccionando cualquier substring «10» y eliminando cualquiera de los caracteres de esa substring , cualquier cantidad de veces.

Ejemplos:

Entrada: S = “0101”
Salida: 001
Explicación:
Al eliminar S[1](=1) de la substring, “10” sobre el rango [1, 2] modifica la string S a “001”, que es la más pequeña .

Entrada: S =”11001101″
Salida: 0001
Explicación:
Una forma posible de obtener lexicográficamente la string más pequeña es:

1. Al quitar S[1](=1) de la substring, “10” sobre el rango [1, 2], se modifica la string S como S = “1001101”.
2. Al eliminar S[0](=1) de la substring, “10” sobre el rango [0, 1] modifica la string S como S = “001101”.
3. Al quitar S[3](=1) de la substring, “10” sobre el rango [3, 4], se modifica la string S como S = “00101”.
4. Al quitar S[2](=1) de la substring, “10” sobre el rango [2, 3], se modifica la string S como S = “0001”.
5. Ahora no se puede eliminar ningún personaje.

Por lo tanto, la string obtenida lexicográficamente más pequeña es “0001”.

 Enfoque: El problema dado se puede resolver con base en las siguientes observaciones: 

• Se puede observar que el carácter ‘ 1 ‘ después del último cero no se puede eliminar ya que no se podrá encontrar ninguna substring “ 10 ”.
• Lexicográficamente, la string más pequeña contendrá tanto como pueda cero antes que la primera.
• Se puede observar que todo ‘ 1 ‘ se puede borrar si hay al menos un ‘ 0 ‘ después.
• Por lo tanto, la idea es eliminar todos los que están antes del último ‘ 0 ‘ de la string.

Siga los pasos a continuación para resolver el problema:

• Inicialice dos variables, digamos ans y LastZe, para almacenar la string resultante y el índice del último ‘ 0 ‘ que ocurrió.
• Itere sobre los caracteres de la string S usando la variable i y luego, si S[i] es ‘ 0 ‘, entonces asigne i a LastZe.
• Itere sobre los caracteres de la string S usando la variable i y realice las siguientes operaciones:
  • Si S[i] = ‘0’ e i ≤ LastZe, agregue S[i] a la respuesta.
  • De lo contrario, si i > LastZe, agregue S[i] a ans .
• Finalmente, después de completar los pasos anteriores, imprima el resultado como ans .

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 smallest lexicogra-
// phically smallest string
string lexicographicallySmallestString(string S, int N)
{
    // Stores the index of last
    // occuring 0
    int LastZe = -1;
 
    // Stores the lexicographically
    // smallest string
    string ans;
 
    // Traverse the string S
    for (int i = N - 1; i >= 0; i--) {
 
        // If str[i] is 0
        if (S[i] == '0') {
 
            // Assign i to lastZe
            LastZe = i;
            break;
        }
    }
 
    // Traverse the string str
    for (int i = 0; i < N; i++) {
 
        // If i is less than or equal
        // to lastZe and str[i] is 0
        if (i <= LastZe && S[i] == '0')
            ans += S[i];
 
        // If i is greater than lastZe
        else if (i > LastZe)
            ans += S[i];
    }
 
    // Return ans
    return ans;
}
 
// Driver Code
int main()
{
    // Input
    string S = "11001101";
    int N = S.size();
 
    // Function Call
    cout << lexicographicallySmallestString(S, N);
 
    return 0;
}

// Java program for the above approach
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to find smallest lexicogra-
// phically smallest string
static String lexicographicallySmallestString(String S,
                                              int N)
{
     
    // Stores the index of last
    // occuring 0
    int LastZe = -1;
 
    // Stores the lexicographically
    // smallest string
    String ans = "";
 
    // Traverse the string S
    for(int i = N - 1; i >= 0; i--)
    {
         
        // If str[i] is 0
        if (S.charAt(i) == '0')
        {
             
            // Assign i to lastZe
            LastZe = i;
            break;
        }
    }
 
    // Traverse the string str
    for(int i = 0; i < N; i++)
    {
         
        // If i is less than or equal
        // to lastZe and str[i] is 0
        if (i <= LastZe && S.charAt(i) == '0')
            ans += S.charAt(i);
 
        // If i is greater than lastZe
        else if (i > LastZe)
            ans += S.charAt(i);
    }
     
    // Return ans
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
     
    // Input
    String S = "11001101";
    int N = S.length();
 
    // Function Call
    System.out.println(
        lexicographicallySmallestString(S, N));
}
}
 
// This code is contributed by avijitmondal1998

# Python program for the above approach
 
# Function to find smallest lexicogra-
# phically smallest string
def lexicographicallySmallestString(S, N):
   
    # Stores the index of last
    # occuring 0
    LastZe = -1
 
    # Stores the lexicographically
    # smallest string
    ans = ""
 
    # Traverse the S
    for i in range(N - 1, -1, -1):
       
        # If str[i] is 0
        if (S[i] == '0'):
 
            # Assign i to lastZe
            LastZe = i
            break
 
    # Traverse the str
    for  i in range(N):
        # If i is less than or equal
        # to lastZe and str[i] is 0
        if (i <= LastZe and S[i] == '0'):
            ans += S[i]
 
        # If i is greater than lastZe
        elif (i > LastZe):
            ans += S[i]
 
    # Return ans
    return ans
 
# Driver Code
if __name__ == '__main__':
    # Input
    S = "11001101"
    N = len(S)
 
    # Function Call
    print (lexicographicallySmallestString(S, N))
 
# This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
class GFG {
    // Function to find smallest lexicogra-
    // phically smallest string
    static string lexicographicallySmallestString(string S,
                                                  int N)
    {
        // Stores the index of last
        // occuring 0
        int LastZe = -1;
 
        // Stores the lexicographically
        // smallest string
        string ans = "";
 
        // Traverse the string S
        for (int i = N - 1; i >= 0; i--) {
 
            // If str[i] is 0
            if (S[i] == '0') {
 
                // Assign i to lastZe
                LastZe = i;
                break;
            }
        }
 
        // Traverse the string str
        for (int i = 0; i < N; i++) {
 
            // If i is less than or equal
            // to lastZe and str[i] is 0
            if (i <= LastZe && S[i] == '0')
                ans += S[i];
 
            // If i is greater than lastZe
            else if (i > LastZe)
                ans += S[i];
        }
 
        // Return ans
        return ans;
    }
 
    // Driver Code
    public static void Main()
    {
        // Input
        string S = "11001101";
        int N = S.Length;
 
        // Function Call
        Console.Write(
            lexicographicallySmallestString(S, N));
    }
}
 
// This code is contributed by ukasp.

<script>
 
// JavaScript program for the above approach
 
// Function to find smallest lexicogra-
// phically smallest string
function lexicographicallySmallestString(S, N)
{
     
    // Stores the index of last
    // occuring 0
    var LastZe = -1;
 
    // Stores the lexicographically
    // smallest string
    var ans = "";
 
    // Traverse the string S
    for(var i = N - 1; i >= 0; i--)
    {
         
        // If str[i] is 0
        if (S.charAt(i) == '0')
        {
             
            // Assign i to lastZe
            LastZe = i;
            break;
        }
    }
 
    // Traverse the string str
    for(var i = 0; i < N; i++)
    {
         
        // If i is less than or equal
        // to lastZe and str[i] is 0
        if (i <= LastZe && S.charAt(i) == '0')
            ans += S.charAt(i);
 
        // If i is greater than lastZe
        else if (i > LastZe)
            ans += S.charAt(i);
    }
     
    // Return ans
    return ans;
}
 
// Driver code
 
// Input
var S = "11001101";
var N = S.length;
 
// Function Call
document.write(lexicographicallySmallestString(S, N));
 
// This code is contributed by shivanisinghss2110
 
</script>

0001

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