Given a string S, print those permutations of string S which are lexicographically greater than S. If there is no such permutation of string, print -1.
Examples:
Input : BCA
Output : CAB, CBA
Explanation: Here, S = “BCA”, and there are 2 strings “CAB, CBA” which are lexicographically greater than S.Input : CBA
Output : -1 There is no string which is lexicographically greater than S, so the output is -1.
Approach: To solve the problem mentioned above we will use STL. Use next_permuation() and prev_permutation() functions to check and the lexicographically greater strings. If the string is greater then print it otherwise print -1. Below is the implementation of above approach:
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 stringvoid 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 Codeint main(){ string S = "ABC"; print_lexiStrings(S);} |
Java
import java.util.*;public class Main { // Function to print the lexicographically // greater strings then the given string public static void printLexiStrings(String S) { // Convert the string to a character array char[] charArray = S.toCharArray(); // Condition to check if there is no // string which is lexicographically // greater than string S boolean hasNext = true; for (int i = charArray.length - 2; i >= 0; i--) { if (charArray[i] < charArray[i + 1]) { int j = charArray.length - 1; while (charArray[j] <= charArray[i]) { j--; } swap(charArray, i, j); reverse(charArray, i + 1, charArray.length - 1); hasNext = false; break; } } if (hasNext) { System.out.println(-1); } // Iterate over all the // lexicographically greater strings while (!hasNext) { System.out.println(new String(charArray)); hasNext = true; for (int i = charArray.length - 2; i >= 0; i--) { if (charArray[i] < charArray[i + 1]) { int j = charArray.length - 1; while (charArray[j] <= charArray[i]) { j--; } swap(charArray, i, j); reverse(charArray, i + 1, charArray.length - 1); hasNext = false; break; } } } } // Utility function to swap two characters in an array private static void swap(char[] charArray, int i, int j) { char temp = charArray[i]; charArray[i] = charArray[j]; charArray[j] = temp; } // Utility function to reverse the subarray from index i to j private static void reverse(char[] charArray, int i, int j) { while (i < j) { swap(charArray, i, j); i++; j--; } } // Driver Code public static void main(String[] args) { String S = "ABC"; printLexiStrings(S); }} |
Python3
import itertools# Define a function that finds lexicographically greater permutations of the given stringdef print_lexiStrings(S): # Convert the string into a list of characters S_list = list(S) # Use the itertools.permutations function to generate all permutations of the list of characters # and keep only the ones that are lexicographically greater than the original string lex_greater_permutations = [''.join(perm) for perm in itertools.permutations(S_list) if perm > tuple(S_list)] # If there are any permutations that are lexicographically greater than the original string, print them if lex_greater_permutations: for perm in lex_greater_permutations: print(perm) # If there are no permutations that are lexicographically greater than the original string, print -1 else: print(-1)# Driver Codeif __name__ == "__main__": # Test the function with an example string S = "ABC" print_lexiStrings(S) |
C#
using System;using System.Linq;class Program{ static void print_lexiStrings(string S) { // Convert the string to a character array char[] arr = S.ToCharArray(); // Condition to check if there is no // string which is lexicographically // greater than string S if (!next_permutation(arr)) Console.WriteLine("-1"); // Move to the previous permutation prev_permutation(arr); // Iterate over all the // lexicographically greater strings while (next_permutation(arr)) { Console.WriteLine(new string(arr)); } } static bool next_permutation(char[] arr) { int i = arr.Length - 2; while (i >= 0 && arr[i] >= arr[i + 1]) { i--; } if (i < 0) { return false; } int j = arr.Length - 1; while (j > i && arr[j] <= arr[i]) { j--; } swap(arr, i, j); reverse(arr, i + 1, arr.Length - 1); return true; } static void prev_permutation(char[] arr) { int i = arr.Length - 2; while (i >= 0 && arr[i] <= arr[i + 1]) { i--; } if (i < 0) { return; } int j = arr.Length - 1; while (j > i && arr[j] >= arr[i]) { j--; } swap(arr, i, j); reverse(arr, i + 1, arr.Length - 1); } static void swap(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } static void reverse(char[] arr, int i, int j) { while (i < j) { swap(arr, i, j); i++; j--; } } static void Main(string[] args) { string S = "ABC"; print_lexiStrings(S); }} |
Javascript
function printLexiStrings(S) { // Convert the string to a character array let charArray = S.split(''); // Condition to check if there is no // string which is lexicographically // greater than string S let hasNext = true; for (let i = charArray.length - 2; i >= 0; i--) { if (charArray[i] < charArray[i + 1]) { let j = charArray.length - 1; while (charArray[j] <= charArray[i]) { j--; } swap(charArray, i, j); reverse(charArray, i + 1, charArray.length - 1); hasNext = false; break; } } if (hasNext) { console.log(-1); } // Iterate over all the // lexicographically greater strings while (!hasNext) { console.log(charArray.join('')); hasNext = true; for (let i = charArray.length - 2; i >= 0; i--) { if (charArray[i] < charArray[i + 1]) { let j = charArray.length - 1; while (charArray[j] <= charArray[i]) { j--; } swap(charArray, i, j); reverse(charArray, i + 1, charArray.length - 1); hasNext = false; break; } } }}// Utility function to swap two characters in an arrayfunction swap(charArray, i, j) { let temp = charArray[i]; charArray[i] = charArray[j]; charArray[j] = temp;}// Utility function to reverse the subarray from index i to jfunction reverse(charArray, i, j) { while (i < j) { swap(charArray, i, j); i++; j--; }}// Driver Codelet S = "ABC";printLexiStrings(S); |
Output
ACB BAC BCA CAB CBA
Time Complexity : O(N*N!), As next_permutation takes O(N!) for finding all the permutations and in order to print the string it will take O(N) time complexity, where N is the length of the string.
Auxiliary Space : O(1)
New Approach:- Here, another approach to solve This program prints all the lexicographically greater permutations of a given string using the following algorithm:
1. Initialize a flag variable “found” to false.
2. Start a do-while loop that runs until a greater permutation is not found.
3. Find the largest index k such that S[k] < S[k+1] by iterating over the string from left to right.
4. If no such index exists, break out of the loop because the given permutation is already the largest possible.
5. Find the largest index l such that S[k] < S[l] by iterating over the string from k+1 to the end.
6. Swap S[k] and S[l].
7. Reverse the sequence from S[k+1] up to the end of the string.
8. Print the lexicographically greater string.
9. Set the flag to true.
10. Repeat the above steps until there are no more greater permutations left.
11. If no greater permutation was found, print -1.
In this way, the program prints all the lexicographically greater permutations of the given string.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to print all the lexicographically greater stringsvoid print_lexiStrings(string S){ int n = S.size(); // Flag variable to keep track of whether a greater permutation was found bool found = false; do { // Find the largest index k such that S[k] < S[k+1] int k = -1; for (int i = 0; i < n - 1; i++) { if (S[i] < S[i+1]) k = i; } // If no such index exists, the permutation is already the largest possible if (k == -1) break; // Find the largest index l such that S[k] < S[l] int l = -1; for (int i = k+1; i < n; i++) { if (S[k] < S[i]) l = i; } // Swap S[k] and S[l] swap(S[k], S[l]); // Reverse the sequence from S[k+1] up to the end of the string reverse(S.begin() + k + 1, S.end()); // Print the lexicographically greater string cout << S << "\n"; // Set the flag to true found = true; } while (found); // If no greater permutation was found, print -1 if (!found) cout << "-1\n";}// Driver Codeint main(){ string S = "ABC"; print_lexiStrings(S); return 0;} |
Java
import java.util.*;public class Main { // Function to print all the lexicographically greater // strings static void printLexiStrings(String s) { char[] S = s.toCharArray(); int n = S.length; // Flag variable to keep track of whether a greater // permutation was found boolean found = false; do { // Find the largest index k such that S[k] < // S[k+1] int k = -1; for (int i = 0; i < n - 1; i++) { if (S[i] < S[i + 1]) k = i; } // If no such index exists, the permutation is // already the largest possible if (k == -1) break; // Find the largest index l such that S[k] < // S[l] int l = -1; for (int i = k + 1; i < n; i++) { if (S[k] < S[i]) l = i; } // Swap S[k] and S[l] char temp = S[k]; S[k] = S[l]; S[l] = temp; // Reverse the sequence from S[k+1] up to the // end of the array for (int i = k + 1, j = n - 1; i < j; i++, j--) { temp = S[i]; S[i] = S[j]; S[j] = temp; } // Print the lexicographically greater string System.out.println(String.valueOf(S)); // Set the flag to true found = true; } while (found); // If no greater permutation was found, print -1 if (!found) System.out.println("-1"); } // Driver Code public static void main(String[] args) { String S = "ABC"; printLexiStrings(S); }} |
Python3
# Pytho program for above approachdef print_lexi_strings(S): n = len(S) found = False while True: # Find the largest index k such that S[k] < S[k+1] k = -1 for i in range(n - 1): if S[i] < S[i + 1]: k = i # If no such index exists, break the loop if k == -1: break # Find the largest index l such that S[k] < S[l] l = -1 for i in range(k + 1, n): if S[k] < S[i]: l = i # Swap S[k] and S[l] S_list = list(S) S_list[k], S_list[l] = S_list[l], S_list[k] S = ''.join(S_list) # Reverse the sequence from S[k+1] up to the end of the string S = S[:k + 1] + S[k + 1:][::-1] # Print the lexicographically greater string print(S) # Set the flag to True found = True # If no greater permutation was found, print -1 if not found: print("-1")# Driver Codeif __name__ == "__main__": S = "ABC" print_lexi_strings(S) |
C#
using System;class Program{ // Function to print all the lexicographically greater strings static void PrintLexiStrings(string s) { int n = s.Length; // Flag variable to keep track of whether a greater permutation was found bool found = false; do { // Find the largest index k such that S[k] < S[k+1] int k = -1; for (int i = 0; i < n - 1; i++) { if (s[i] < s[i + 1]) k = i; } // If no such index exists, the permutation is already the largest possible if (k == -1) break; // Find the largest index l such that S[k] < S[l] int l = -1; for (int i = k + 1; i < n; i++) { if (s[k] < s[i]) l = i; } // Convert the string to a char array for swapping char[] chars = s.ToCharArray(); // Swap S[k] and S[l] char temp = chars[k]; chars[k] = chars[l]; chars[l] = temp; s = new string(chars); // Reverse the sequence from S[k+1] up to the end of the string char[] subArray = s.Substring(k + 1).ToCharArray(); Array.Reverse(subArray); s = s.Substring(0, k + 1) + new string(subArray); // Print the lexicographically greater string Console.WriteLine(s); // Set the flag to true found = true; } while (found); // If no greater permutation was found, print -1 if (!found) Console.WriteLine("-1"); } // Driver Code static void Main() { string S = "ABC"; PrintLexiStrings(S); }}// This code is contributed by Dwaipayan Bandyopadhyay |
Output:-
ACB
BAC
BCA
CAB
CBA
Time complexity:- Time complexity of the given implementation is O(n!), where n is the length of the string. This is because there are n! possible permutations of the string, and we are checking all of them.
Auxiliary Space:- The auxiliary space used by the program is O(n), where n is the length of the string. This is because we are only storing the input string and a few integer variables. Therefore, the space complexity is constant with respect to the input size.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
