Print the last character of lexicographically smallest non-palindromic permutation of a string
Given string str, the task is to print the last character of the lexicographically smallest non-palindromic permutation of the given string. If no such permutation exists, print “-1”.
Examples:
Input: str = “deepqvu”
Output: v
Explanation: The string “deepquv” is the lexicographically smallest permutation which is not a palindrome.
Therefore, the last character is v.Input: str = “zyxaaabb”
Output: z
Explanation: The string “aaabbxyz” is the lexicographically smallest permutation which is not a palindrome.
Therefore, the last character is z.
Naive Approach: The simplest approach to solve the problem is to generate all possible permutations of the given string and for each permutation, check if it is a palindrome or not. Among all non-palindromic permutations obtained, print the last character of lexicographically the smallest permutation. Follow the steps below:
- Sort the given string str.
- Check all the subsequent permutations of the string for the palindrome using a function next_permutation().
- If there exists any permutation which is non-palindromic, then print its last character.
- Otherwise, print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check whether a string // s is a palindrome or not bool isPalin(string s, int N) { // Traverse the string for ( int i = 0; i < N; i++) { // If unequal character if (s[i] != s[N - i - 1]) { return false ; } } return true ; } // Function to find the smallest // non-palindromic lexicographic // permutation of string s void lexicographicSmallestString( string s, int N) { // Base Case if (N == 1) { cout << "-1" ; } // Sort the given string sort(s.begin(), s.end()); int flag = 0; // If the formed string is // non palindromic if (isPalin(s, N) == false ) flag = 1; if (!flag) { // Check for all permutations while (next_permutation(s.begin(), s.end())) { // Check palindromic if (isPalin(s, N) == false ) { flag = 1; break ; } } } // If non palindromic string found // print its last character if (flag == 1) { int lastChar = s.size() - 1; cout << s[lastChar] << ' ' ; } // Otherwise, print "-1" else { cout << "-1" ; } } // Driver Code int main() { // Given string str string str = "deepqvu" ; // Length of the string int N = str.length(); // Function Call lexicographicSmallestString(str, N); return 0; } |
Java
// Java program for the // above approach import java.util.*; class GFG{ // Function to check whether // a String s is a palindrome // or not static boolean isPalin(String s, int N) { // Traverse the String for ( int i = 0 ; i < N; i++) { // If unequal character if (s.charAt(i) != s.charAt(N - i - 1 )) { return false ; } } return true ; } static boolean next_permutation( char [] p) { for ( int a = p.length - 2 ; a >= 0 ; --a) if (p[a] < p[a + 1 ]) for ( int b = p.length - 1 ;; --b) if (p[b] > p[a]) { char t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.length - 1 ; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true ; } return false ; } //Method to sort a string alphabetically static String sortString(String inputString) { // convert input string // to char array char tempArray[] = inputString.toCharArray(); // Sort tempArray Arrays.sort(tempArray); // Return new sorted string return new String(tempArray); } // Function to find the smallest // non-palindromic lexicographic // permutation of String s static void lexicographicSmallestString(String s, int N) { // Base Case if (N == 1 ) { System.out.print( "-1" ); } // Sort the given String s = sortString(s); int flag = 0 ; // If the formed String is // non palindromic if (isPalin(s, N) == false ) flag = 1 ; if (flag != 0 ) { // Check for all permutations while (next_permutation(s.toCharArray())) { // Check palindromic if (isPalin(s, N) == false ) { flag = 1 ; break ; } } } // If non palindromic String found // print its last character if (flag == 1 ) { int lastChar = s.length() - 1 ; System.out.print(s.charAt(lastChar) + " " ); } // Otherwise, print "-1" else { System.out.print( "-1" ); } } // Driver Code public static void main(String[] args) { // Given String str String str = "deepqvu" ; // Length of the String int N = str.length(); // Function Call lexicographicSmallestString(str, N); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program for the # above approach # Function to check whether # a String s is a palindrome # or not def isPalin(s, N): # Traverse the String for i in range (N): # If unequal character if (s[i] ! = s[N - i - 1 ]): return False ; return True ; def next_permutation(p): for a in range ( len (p) - 2 , 0 , - 1 ): if (p[a] < p[a + 1 ]): for b in range ( len (p) - 1 , - 1 ): if (p[b] > p[a]): t = p[a]; p[a] = p[b]; p[b] = t; for a in range (a + 1 , a < b,): b = len (p) - 1 ; if (a < b): t = p[a]; p[a] = p[b]; p[b] = t; b - = 1 ; return True ; return False ; # Method to sort a string # alphabetically def sortString(inputString): # convert input string # to char array # Sort tempArray tempArray = ''.join( sorted (inputString)); # Return new sorted string return tempArray; # Function to find the smallest # non-palindromic lexicographic # permutation of String s def lexicographicSmallestString(s, N): # Base Case if (N = = 1 ): print ( "-1" ); # Sort the given String s = sortString(s); flag = 0 ; # If the formed String is # non palindromic if (isPalin(s, N) = = False ): flag = 1 ; if (flag ! = 0 ): # Check for all permutations while (next_permutation(s)): # Check palindromic if (isPalin(s, N) = = False ): flag = 1 ; break ; # If non palindromic String # found print last character if (flag = = 1 ): lastChar = len (s) - 1 ; print (s[lastChar], end = ""); # Otherwise, pr"-1" else : print ( "-1" ); # Driver Code if __name__ = = '__main__' : # Given String str str = "deepqvu" ; # Length of the String N = len ( str ); # Function Call lexicographicSmallestString( str , N); # This code is contributed by shikhasingrajput |
C#
// C# program for the // above approach using System; class GFG{ // Function to check whether // a String s is a palindrome // or not static bool isPalin(String s, int N) { // Traverse the String for ( int i = 0; i < N; i++) { // If unequal character if (s[i] != s[N - i - 1]) { return false ; } } return true ; } static bool next_permutation( char [] p) { for ( int a = p.Length - 2; a >= 0; --a) if (p[a] < p[a + 1]) for ( int b = p.Length - 1;; --b) if (p[b] > p[a]) { char t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.Length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true ; } return false ; } //Method to sort a string alphabetically static String sortString(String inputString) { // convert input string // to char array char []tempArray = inputString.ToCharArray(); // Sort tempArray Array.Sort(tempArray); // Return new sorted string return new String(tempArray); } // Function to find the smallest // non-palindromic lexicographic // permutation of String s static void lexicographicSmallestString(String s, int N) { // Base Case if (N == 1) { Console.Write( "-1" ); } // Sort the given String s = sortString(s); int flag = 0; // If the formed String is // non palindromic if (isPalin(s, N) == false ) flag = 1; if (flag != 0) { // Check for all permutations while (next_permutation(s.ToCharArray())) { // Check palindromic if (isPalin(s, N) == false ) { flag = 1; break ; } } } // If non palindromic String found // print its last character if (flag == 1) { int lastChar = s.Length - 1; Console.Write(s[lastChar] + " " ); } // Otherwise, print "-1" else { Console.Write( "-1" ); } } // Driver Code public static void Main(String[] args) { // Given String str String str = "deepqvu" ; // Length of the String int N = str.Length; // Function Call lexicographicSmallestString(str, N); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // JavaScript program for the // above approach // Function to check whether // a String s is a palindrome // or not function isPalin(s, N) { // Traverse the String for ( var i = 0; i < N; i++) { // If unequal character if (s[i] !== s[N - i - 1]) { return false ; } } return true ; } function next_permutation(p) { for ( var a = p.length - 2; a >= 0; --a) if (p[a] < p[a + 1]) for ( var b = p.length - 1; ; --b) if (p[b] > p[a]) { var t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true ; } return false ; } //Method to sort a string alphabetically function sortString(inputString) { // convert input string // to char array var tempArray = inputString.split( "" ); // Sort tempArray tempArray.sort(); // Return new sorted string return tempArray.join( "" ); } // Function to find the smallest // non-palindromic lexicographic // permutation of String s function lexicographicSmallestString(s, N) { // Base Case if (N === 1) { document.write( "-1" ); } // Sort the given String s = sortString(s); var flag = 0; // If the formed String is // non palindromic if (isPalin(s, N) === false ) flag = 1; if (flag !== 0) { // Check for all permutations while (next_permutation(s.split( "" ))) { // Check palindromic if (isPalin(s, N) === false ) { flag = 1; break ; } } } // If non palindromic String found // print its last character if (flag === 1) { var lastChar = s.length - 1; document.write(s[lastChar] + " " ); } // Otherwise, print "-1" else { document.write( "-1" ); } } // Driver Code // Given String str var str = "deepqvu" ; // Length of the String var N = str.length; // Function Call lexicographicSmallestString(str, N); </script> |
v
Time Complexity: O(N*N!)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to store the frequencies of each character of the given string str. If all the characters are the same, then print “-1”. Otherwise, print the largest character of the given string str.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the smallest non // palindromic lexicographic string void lexicographicSmallestString( string s, int N) { // Stores the frequency of each // character of the string s map< char , int > M; // Traverse the string for ( char ch : s) { M[ch]++; } // If there is only one element if (M.size() == 1) { cout << "-1" ; } // Otherwise else { auto it = M.rbegin(); cout << it->first; } } // Driver Code int main() { // Given string str string str = "deepqvu" ; // Length of the string int N = str.length(); // Function Call lexicographicSmallestString(str, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG{ // Function to find the smallest non // palindromic lexicographic string static void lexicographicSmallestString(String s, int N) { // Stores the frequency of each // character of the string s SortedMap<Character, Integer> M = new TreeMap<Character, Integer>(); // Converting given string to char array char [] str = s.toCharArray(); // Traverse the string for ( char c : str) { if (M.containsKey(c)) { // If char is present in M M.put(c, M.get(c) + 1 ); } else { // If char is not present in M M.put(c, 1 ); } } // If there is only one element if (M.size() == 1 ) { System.out.print( "-1" ); } // Otherwise else { System.out.print( M.lastKey() ); } } // Driver Code public static void main (String[] args) { // Given string str String str = "deepqvu" ; // Length of the string int N = str.length(); // Function Call lexicographicSmallestString(str, N); } } // This code is contributed by math_lover |
Python3
# Python3 program for the above approach # Function to find the smallest non # palindromic lexicographic string def lexicographicSmallestString(s, N): # Stores the frequency of each # character of the s M = {} # Traverse the string for ch in s: M[ch] = M.get(ch, 0 ) + 1 # If there is only one element if len (M) = = 1 : print ( "-1" ) # Otherwise else : x = list (M.keys())[ - 2 ] print (x) # Driver Code if __name__ = = '__main__' : # Given str str = "deepqvu" # Length of the string N = len ( str ) # Function call lexicographicSmallestString( str , N) # This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approach using System; using System.Collections.Generic; class GFG{ // Function to find the smallest non // palindromic lexicographic string static void lexicographicSmallestString(String s, int N) { // Stores the frequency of each // character of the string s SortedDictionary< char , int > M = new SortedDictionary< char , int >(); // Converting given string // to char array char [] str = s.ToCharArray(); // Traverse the string foreach ( char c in str) { if (M.ContainsKey(c)) { // If char is present // in M M = M + 1; } else { // If char is not present // in M M.Add(c, 1); } } // If there is only // one element if (M.Count == 1) { Console.Write( "-1" ); } // Otherwise else { int count = 0; foreach (KeyValuePair< char , int > m in M) { count++; if (count == M.Count) Console.Write(m.Key); } } } // Driver Code public static void Main(String[] args) { // Given string str String str = "deepqvu" ; // Length of the string int N = str.Length; // Function Call lexicographicSmallestString(str, N); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // Javascript program for the above approach // Function to find the smallest non // palindromic lexicographic string function lexicographicSmallestString(s,N) { // Stores the frequency of each // character of the string s let M = new Map(); // Converting given string to char array let str = s.split( "" ); // Traverse the string for (let c=0;c< str.length;c++) { if (M.has(str)) { // If char is present in M M.set(str, M.get(str) + 1); } else { // If char is not present in M M.set(str, 1); } } // If there is only one element if (M.size == 1) { document.write( "-1" ); } // Otherwise else { let temp=Array.from(M) document.write( temp[temp.length-2][0] ); } } // Driver Code let str = "deepqvu" ; let N = str.length; // Function Call lexicographicSmallestString(str, N); // This code is contributed by patel2127 </script> |
v
Time Complexity: O(N)
Auxiliary Space: O(26)