Compruebe si una string binaria se puede ordenar en orden decreciente eliminando los caracteres no adyacentes

Dada una string binaria S de tamaño N , la tarea es verificar si la string binaria S se puede ordenar en orden decreciente eliminando cualquier número de caracteres no adyacentes. Si es posible clasificar la string en orden decreciente, imprima «Sí» . De lo contrario, escriba “No” .

Ejemplos:

Entrada: S= “10101011011”
Salida: Sí
Explicación:
Después de eliminar los caracteres no adyacentes en los índices 1, 3, 5 y 8, modifica la string a “1111111”, que se ordena en orden decreciente. Por lo tanto, imprima «Sí».

Entrada: S = “0011”
Salida: No

Enfoque: El problema dado se puede resolver en base a las observaciones de que si existen dos caracteres adyacentes que tienen 1 y luego existen caracteres adyacentes que tienen 0 , entonces es imposible ordenar la string eliminando los caracteres no adyacentes . Siga los pasos a continuación para resolver el problema:

• Inicialice una variable booleana, diga marcar como verdadero que almacena el estado si la string dada se puede ordenar o no.
• Atraviese la string S dada desde el final y, si existe algún par de caracteres adyacentes que tengan valores 1s , almacene el segundo índice de 1 en una variable, digamos idx , y salga del bucle .
• Recorra la string dada S nuevamente desde atrás sobre el rango [idx, 0] y si existe algún par de caracteres adyacentes que tengan valores 0 , actualice el valor de la bandera como falso y salga del ciclo .
• Después de completar los pasos anteriores, si el valor de la bandera es verdadero , imprima «Sí» . De lo contrario, escriba “No” .

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 sort the given string in
// decreasing order by removing the non
// adjacent characters
string canSortString(string S, int N)
{
    // Keeps the track whether the
    // string can be sorted or not
    int flag = 1;
 
    int i, j;
 
    // Traverse the given string S
    for (i = N - 2; i >= 0; i--) {
 
        // Check if S[i] and
        // S[i + 1] are both '1'
        if (S[i] == '1'
            && S[i + 1] == '1') {
            break;
        }
    }
 
    // Traverse the string S from
    // the indices i to 0
    for (int j = i; j >= 0; j--) {
 
        // If S[j] and S[j + 1] is
        // equal to 0
        if (S[j] == '0'
            && S[j + 1] == '0') {
 
            // Mark flag false
            flag = 0;
            break;
        }
    }
 
    // If flag is 0, then it is not
    // possible to sort the string
    if (flag == 0) {
        return "No";
    }
 
    // Otherwise
    else {
        return "Yes";
    }
}
 
// Driver Code
int main()
{
    string S = "10101011011";
    int N = S.length();
    cout << canSortString(S, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG
{
 
  // Function to sort the given string in
// decreasing order by removing the non
// adjacent characters
static String canSortString(String S, int N)
{
   
    // Keeps the track whether the
    // string can be sorted or not
    int flag = 1;
 
    int i, j;
 
    // Traverse the given string S
    for (i = N - 2; i >= 0; i--) {
 
        // Check if S[i] and
        // S[i + 1] are both '1'
        if (S.charAt(i) == '1'
            && S.charAt(i + 1) == '1') {
            break;
        }
    }
 
    // Traverse the string S from
    // the indices i to 0
    for ( j = i; j >= 0; j--) {
 
        // If S[j] and S[j + 1] is
        // equal to 0
        if (S.charAt(j) == '0'
            && S.charAt(j + 1) == '0') {
 
            // Mark flag false
            flag = 0;
            break;
        }
    }
 
    // If flag is 0, then it is not
    // possible to sort the string
    if (flag == 0) {
        return "No";
    }
 
    // Otherwise
    else {
        return "Yes";
    }
}
 
    public static void main (String[] args) {
      String S = "10101011011";
    int N = S.length();
    System.out.println(canSortString(S, N));
   
    }
}
 
// This code is contributed by offbeat

# Python3 program for the above approach
 
# Function to sort the given string in
# decreasing order by removing the non
# adjacent characters
def canSortString(S, N):
     
    # Keeps the track whether the
    # string can be sorted or not
    flag = 1
 
    # Traverse the given string S
    i = N - 2
     
    while(i >= 0):
         
        # Check if S[i] and
        # S[i + 1] are both '1'
        if (S[i] == '1' and S[i + 1] == '1'):
            break
         
        i -= 1
 
    # Traverse the string S from
    # the indices i to 0
    j = i
     
    while(j >= 0):
         
        # If S[j] and S[j + 1] is
        # equal to 0
        if (S[j] == '0' and S[j + 1] == '0'):
             
            # Mark flag false
            flag = 0
            break
         
        j -= 1
 
    # If flag is 0, then it is not
    # possible to sort the string
    if (flag == 0):
        return "No"
 
    # Otherwise
    else:
        return "Yes"
 
# Driver Code
if __name__ == '__main__':
     
    S = "10101011011"
    N = len(S)
     
    print(canSortString(S, N))
 
# This code is contributed by ipg2016107

// C# program for the above approach
using System;
 
class GFG{
 
// Function to sort the given string in
// decreasing order by removing the non
// adjacent characters
static string canSortString(string S, int N)
{
     
    // Keeps the track whether the
    // string can be sorted or not
    int flag = 1;
 
    int i, j;
 
    // Traverse the given string S
    for(i = N - 2; i >= 0; i--)
    {
         
        // Check if S[i] and
        // S[i + 1] are both '1'
        if (S[i] == '1' && S[i + 1] == '1')
        {
            break;
        }
    }
 
    // Traverse the string S from
    // the indices i to 0
    for(j = i; j >= 0; j--)
    {
         
        // If S[j] and S[j + 1] is
        // equal to 0
        if (S[j] == '0' && S[j + 1] == '0')
        {
             
            // Mark flag false
            flag = 0;
            break;
        }
    }
 
    // If flag is 0, then it is not
    // possible to sort the string
    if (flag == 0)
    {
        return "No";
    }
 
    // Otherwise
    else
    {
        return "Yes";
    }
}
 
// Driver code
public static void Main(string[] args)
{
    string S = "10101011011";
    int N = S.Length;
     
    Console.WriteLine(canSortString(S, N));
}
}
 
// This code is contributed by ukasp

<script>
// Javascript program for the above approach
 
// Function to sort the given string in
// decreasing order by removing the non
// adjacent characters
function canSortString(S, N)
{
    // Keeps the track whether the
    // string can be sorted or not
    let flag = 1;
 
    let i, j;
 
    // Traverse the given string S
    for (let i = N - 2; i >= 0; i--) {
 
        // Check if S[i] and
        // S[i + 1] are both '1'
        if (S[i] == '1'
            && S[i + 1] == '1') {
            break;
        }
    }
 
    // Traverse the string S from
    // the indices i to 0
    for (let j = i; j >= 0; j--) {
 
        // If S[j] and S[j + 1] is
        // equal to 0
        if (S[j] == '0'
            && S[j + 1] == '0') {
 
            // Mark flag false
            flag = 0;
            break;
        }
    }
 
    // If flag is 0, then it is not
    // possible to sort the string
    if (flag == 0) {
        return "No";
    }
 
    // Otherwise
    else {
        return "Yes";
    }
}
 
// Driver Code
    let S = "10101011011";
    let N = S.length;
    document.write(canSortString(S, N));
 
// This code is contributed by gfgking
</script>

Yes

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