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); }
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)