Imprime todas las permutaciones lexicográficas mayores de una string dada

Dada una string S , imprime aquellas permutaciones de la string S que son lexicográficamente mayores que S. Si no existe tal permutación de string, imprime -1. Ejemplos:

Entrada: BCA Salida: CAB, CBA Explicación: Aquí, S = “BCA”, y hay 2 strings “CAB, CBA” que son lexicográficamente mayores que S. Entrada: CBA Salida: -1 No hay ninguna string que sea lexicográficamente mayor que S, por lo que la salida es -1.

Planteamiento: Para solucionar el problema mencionado anteriormente utilizaremos STL . Use las funciones next_permuation() y prev_permutation() para verificar las strings lexicográficamente más grandes. Si la string es mayor, imprímala; de lo contrario, imprima -1. A continuación se muestra la implementación del enfoque anterior: 

CPP

// C++ program to print the lexicographically
// greater strings then the given string
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the lexicographically
// greater strings then the given string
void print_lexiStrings(string S)
{
 
    // Condition to check if there is no
    // string which is lexicographically
    // greater than string S
    if (!next_permutation(S.begin(), S.end()))
        cout<<-1<<endl;
 
    // Move to the previous permutation
    prev_permutation(S.begin(), S.end());
 
    // Iterate over all the
    // lexicographically greater strings
    while (next_permutation(S.begin(), S.end())) {
        cout<<S<<endl;
    }
}
 
// Driver Code
int main()
{
 
    string S = "ABC";
 
    print_lexiStrings(S);
}
Producción

ACB
BAC
BCA
CAB
CBA

Complejidad de tiempo: O(N*N!), Como next_permutation toma O(N!) para encontrar todas las permutaciones y para imprimir la string tomará O(N) complejidad de tiempo, donde N es la longitud de la string.
Espacio Auxiliar : O(1)

Publicación traducida automáticamente

Artículo escrito por yatinagg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *