Given string str consisting of lowercase alphabets, the task is to construct the lexicographically smallest non-palindromic string by swapping any pair of adjacent characters from the string any number of times.
If the given string cannot be converted to a lexicographically smallest non-palindromic string, then print “-1”.
Examples:
Input: str = “djfbw”
Output: bdfjw
Explanation:
Perform the following swap operations to get the lexicographically smallest non-palindromic string:
Swap ‘b’ and ‘f’, str becomes “djbfw”
Swap ‘j’ and ‘b’, str becomes “dbjfw”
Swap ‘b’ and ‘d’, str becomes “bdjfw”
Swap ‘j’ and ‘f’, str becomes “bdfjw”.
Now “bdfjw” is the lexicographically smallest string which is not a palindrome.Input: str[] = “pppppp”
Output: -1
Naive Approach: The idea is to generate all possible permutations of the string and to check if they form palindrome or not. Print the smallest permutation among them.
Time Complexity: O(N*N!)
Auxiliary Space: O(N)
Efficient Approach: The idea is to check if lexicographically the smallest string possible from the given string is a palindrome or not. Below are the steps:
- To obtain lexicographically the smallest string, sort the given string to arrange the characters of the string in increasing order.
- Now, if the sorted string is a palindrome, then it means that the string has only one type of character and it can not be arranged to form a string which is not a palindrome.
- If it is not a palindrome, then the sorted string is lexicographically the smallest string which is not a palindrome.
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 lexicographically// smallest string which is non-palindromevoid smallestNonPalindromic(string& s){ // Sort the given string sort(s.begin(), s.end()); // Store reverse of sorted string string reversestring = string(s.rbegin(), s.rend()); // Check if the sorted string is // palindromic or not if (s != reversestring) { cout << s; } else { cout << "-1"; }}// Driver Codeint main(){ // Given string str string str = "asmfjdeovnhekfnj"; // Function Call smallestNonPalindromic(str); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// reverse stringstatic String reverse(String input){ char[] a = input.toCharArray(); int l, r = a.length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.valueOf(a);}// Method to sort a string alphabeticallystatic 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 lexicographically// smallest String which is non-palindromestatic void smallestNonPalindromic(String s){ // Sort the given String s = sortString(s); // Store reverse of sorted String String reverseString = reverse(s); // Check if the sorted String is // palindromic or not if (s != reverseString) { System.out.print(s); } else { System.out.print("-1"); }}// Driver Codepublic static void main(String[] args){ // Given String str String str = "asmfjdeovnhekfnj"; // Function Call smallestNonPalindromic(str);}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program for the above approach# Function to find the lexicographically# smallest string which is non-palindromedef smallestNonPalindromic(s): # Sort the given string s = sorted(s) # Store reverse of sorted string reversestring = s[::-1] # Check if the sorted string is # palindromic or not if (s != reversestring): print("".join(s)) else: print("-1")# Driver Codeif __name__ == '__main__': # Given string str str = "asmfjdeovnhekfnj" # Function call smallestNonPalindromic(str)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{// Reverse stringstatic String reverse(String input){ char[] a = input.ToCharArray(); int l, r = a.Length - 1; for(l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.Join("", a);}// Method to sort a string alphabeticallystatic 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 lexicographically// smallest String which is non-palindromestatic void smallestNonPalindromic(String s){ // Sort the given String s = sortString(s); // Store reverse of sorted String String reverseString = reverse(s); // Check if the sorted String is // palindromic or not if (s != reverseString) { Console.Write(s); } else { Console.Write("-1"); }}// Driver Codepublic static void Main(String[] args){ // Given String str String str = "asmfjdeovnhekfnj"; // Function call smallestNonPalindromic(str);}}// This code is contributed by Amit Katiyar |
Javascript
<script> // JavaScript program for the above approach // Function to find the lexicographically // smallest string which is non-palindrome function smallestNonPalindromic(s) { var newStr = s.split(""); // Sort the given string newStr.sort().reverse(); // Store reverse of sorted string var reversestring = newStr.reverse().join(""); // Check if the sorted string is // palindromic or not if (s !== reversestring) { document.write(newStr.join("")); } else { document.write("-1"); } } // Driver Code // Given string str var str = "asmfjdeovnhekfnj"; // Function Call smallestNonPalindromic(str); </script> |
Output:
adeeffhjjkmnnosv
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
