Given a string str. The problem is to rearrange characters of the given string such that the vowels and consonants occupy alternate position and the string so formed should be lexicographically (alphabetically) smallest. If string can not be rearranged in desired way, print “no such string”.
Examples:
Input : mango Output : gamon It could be arranged in other ways too, like manog, etc., but gamon is lexicographically smallest. Input : aeroplane Output : alanepero
Approach: Following are the steps:
- Store frequency of each character of input string in a hash table.
- Count number of vowels and consonants in given string.
- If difference between counts is more than one, return “Not Possible”.
- Else, form separate vowel and consonant strings with the help of the hash table having frequencies of each character of the input string. Note, while creating vowel and consonant strings, the characters in respective strings should be in alphabetical order.
- If there are more vowels than consonants, print first vowel first and then print remaining characters from consonant and vowel strings alternately.
- If there are more consonants than vowels, print first consonant first and then print remaining characters from vowel and consonant strings alternately.
- If counts are same, compare first vowel with first consonant and print the smaller one first and then continue printing alternately.
Implementation:
C++
// C++ implementation of lexicographically first// alternate vowel and consonant string#include <bits/stdc++.h>using namespace std;#define SIZE 26// 'ch' is vowel or notbool isVowel(char ch){ if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') return true; return false;}// create alternate vowel and consonant string// str1[0...l1-1] and str2[start...l2-1]string createAltStr(string str1, string str2, int start, int l){ string finalStr = ""; // first adding character of vowel/consonant // then adding character of consonant/vowel for (int i = 0, j = start; j < l; i++, j++) finalStr = (finalStr + str1.at(i)) + str2.at(j); return finalStr;}// function to find the required lexicographically// first alternate vowel and consonant stringstring findAltStr(string str){ // hash table to store frequencies // of each character in 'str' int char_freq[SIZE]; // initialize all elements of char_freq[] // to 0 memset(char_freq, 0, sizeof(char_freq)); int nv = 0, nc = 0; string vstr = "", cstr = ""; int l = str.size(); for (int i = 0; i < l; i++) { char ch = str.at(i); // count vowels if (isVowel(ch)) nv++; // count consonants else nc++; // update frequency of 'ch' in // char_freq[] char_freq[ch - 97]++; } // no such string can be formed if (abs(nv - nc) >= 2) return "no such string"; // form the vowel string 'vstr' and // consonant string 'cstr' which contains // characters in lexicographical order for (int i = 0; i < SIZE; i++) { char ch = (char)(i + 97); for (int j = 1; j <= char_freq[i]; j++) { if (isVowel(ch)) vstr += ch; else cstr += ch; } } // remove first character of vowel string // then create alternate string with // cstr[0...nc-1] and vstr[1...nv-1] if (nv > nc) return (vstr.at(0) + createAltStr(cstr, vstr, 1, nv)); // remove first character of consonant string // then create alternate string with // vstr[0...nv-1] and cstr[1...nc-1] if (nc > nv) return (cstr.at(0) + createAltStr(vstr, cstr, 1, nc)); // if both vowel and consonant // strings are of equal length // start creating string with consonant if (cstr.at(0) < vstr.at(0)) return createAltStr(cstr, vstr, 0, nv); // start creating string with vowel return createAltStr(vstr, cstr, 0, nc);}// Driver program to test aboveint main(){ string str = "aeroplane"; cout << findAltStr(str); return 0;} |
Java
// Java implementation of lexicographically first // alternate vowel and consonant String import java.util.Arrays;class GFG { static final int SIZE = 26; // 'ch' is vowel or not static boolean isVowel(char ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') { return true; } return false; } // create alternate vowel and consonant String // str1[0...l1-1] and str2[start...l2-1] static String createAltStr(String str1, String str2, int start, int l) { String finalStr = ""; // first adding character of vowel/consonant // then adding character of consonant/vowel for (int i = 0, j = start; j < l; i++, j++) { finalStr = (finalStr + str1.charAt(i)) + str2.charAt(j); } return finalStr; } // function to find the required // lexicographically first alternate // vowel and consonant String static String findAltStr(String str) { // hash table to store frequencies // of each character in 'str' int char_freq[] = new int[SIZE]; // initialize all elements of char_freq[] // to 0 Arrays.fill(char_freq, 0); int nv = 0, nc = 0; String vstr = "", cstr = ""; int l = str.length(); for (int i = 0; i < l; i++) { char ch = str.charAt(i); // count vowels if (isVowel(ch)) { nv++; } // count consonants else { nc++; } // update frequency of 'ch' in // char_freq[] char_freq[ch - 97]++; } // no such String can be formed if (Math.abs(nv - nc) >= 2) { return "no such String"; } // form the vowel String 'vstr' and // consonant String 'cstr' which contains // characters in lexicographical order for (int i = 0; i < SIZE; i++) { char ch = (char) (i + 97); for (int j = 1; j <= char_freq[i]; j++) { if (isVowel(ch)) { vstr += ch; } else { cstr += ch; } } } // remove first character of vowel String // then create alternate String with // cstr[0...nc-1] and vstr[1...nv-1] if (nv > nc) { return (vstr.charAt(0) + createAltStr(cstr, vstr, 1, nv)); } // remove first character of consonant String // then create alternate String with // vstr[0...nv-1] and cstr[1...nc-1] if (nc > nv) { return (cstr.charAt(0) + createAltStr(vstr, cstr, 1, nc)); } // if both vowel and consonant // strings are of equal length // start creating String with consonant if (cstr.charAt(0) < vstr.charAt(0)) { return createAltStr(cstr, vstr, 0, nv); } // start creating String with vowel return createAltStr(vstr, cstr, 0, nc); } // Driver code public static void main(String[] args) { String str = "aeroplane"; System.out.println(findAltStr(str)); }} // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of lexicographically first# alternate vowel and consonant stringSIZE = 26# 'ch' is vowel or notdef isVowel(ch): if (ch == 'a' or ch == 'e' or ch == 'i' or ch == 'o' or ch == 'u'): return True return False# create alternate vowel and consonant string# str1[0...l1-1] and str2[start...l2-1]def createAltStr(str1, str2, start, l): finalStr = "" i = 0 j = start # first adding character of vowel/consonant # then adding character of consonant/vowel while j < l: finalStr += str1[i] + str2[j] i += 1 j += 1 return finalStr# function to find the required lexicographically# first alternate vowel and consonant stringdef findAltStr(string): # hash table to store frequencies # of each character in 'str' char_freq = [0] * SIZE # initialize all elements # of char_freq[] to 0 nv = 0 nc = 0 vstr = "" cstr = "" l = len(string) for i in range(l): ch = string[i] # count vowels if isVowel(ch): nv += 1 # count consonants else: nc += 1 # update frequency of 'ch' in # char_freq[] char_freq[ord(ch) - 97] += 1 # no such string can be formed if abs(nv - nc) >= 2: return "no such string" # form the vowel string 'vstr' and # consonant string 'cstr' which contains # characters in lexicographical order for i in range(SIZE): ch = chr(i + 97) for j in range(1, char_freq[i] + 1): if isVowel(ch): vstr += ch else: cstr += ch # remove first character of vowel string # then create alternate string with # cstr[0...nc-1] and vstr[1...nv-1] if nv > nc: return vstr[0] + createAltStr(cstr, vstr, 1, nv) # remove first character of consonant string # then create alternate string with # vstr[0...nv-1] and cstr[1...nc-1] if nc > nv: return cstr[0] + createAltStr(vstr, cstr, 1, nc) # if both vowel and consonant # strings are of equal length # start creating string with consonant if cstr[0] < vstr[0]: return createAltStr(cstr, vstr, 0, nv) # start creating string with vowel return createAltStr(vstr, cstr, 0, nc)# Driver Codeif __name__ == "__main__": string = "aeroplane" print(findAltStr(string))# This code is contributed by# sanjeev2552 |
C#
// C# implementation of lexicographically first // alternate vowel and consonant String using System;class GFG { static readonly int SIZE = 26; // 'ch' is vowel or not static bool isVowel(char ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') { return true; } return false; } // create alternate vowel and consonant String // str1[0...l1-1] and str2[start...l2-1] static String createAltStr(String str1, String str2, int start, int l) { String finalStr = ""; // first adding character of vowel/consonant // then adding character of consonant/vowel for (int i = 0, j = start; j < l; i++, j++) { finalStr = (finalStr + str1[i]) + str2[j]; } return finalStr; } // function to find the required // lexicographically first alternate // vowel and consonant String static String findAltStr(String str) { // hash table to store frequencies // of each character in 'str' int []char_freq = new int[SIZE]; int nv = 0, nc = 0; String vstr = "", cstr = ""; int l = str.Length; for (int i = 0; i < l; i++) { char ch = str[i]; // count vowels if (isVowel(ch)) { nv++; } // count consonants else { nc++; } // update frequency of 'ch' in // char_freq[] char_freq[ch - 97]++; } // no such String can be formed if (Math.Abs(nv - nc) >= 2) { return "no such String"; } // form the vowel String 'vstr' and // consonant String 'cstr' which contains // characters in lexicographical order for (int i = 0; i < SIZE; i++) { char ch = (char) (i + 97); for (int j = 1; j <= char_freq[i]; j++) { if (isVowel(ch)) { vstr += ch; } else { cstr += ch; } } } // remove first character of vowel String // then create alternate String with // cstr[0...nc-1] and vstr[1...nv-1] if (nv > nc) { return (vstr[0] + createAltStr(cstr, vstr, 1, nv)); } // remove first character of consonant String // then create alternate String with // vstr[0...nv-1] and cstr[1...nc-1] if (nc > nv) { return (cstr[0] + createAltStr(vstr, cstr, 1, nc)); } // if both vowel and consonant // strings are of equal length // start creating String with consonant if (cstr[0] < vstr[0]) { return createAltStr(cstr, vstr, 0, nv); } // start creating String with vowel return createAltStr(vstr, cstr, 0, nc); } // Driver code public static void Main(String[] args) { String str = "aeroplane"; Console.WriteLine(findAltStr(str)); }}/* This code has been contributedby PrinciRaj1992*/ |
Javascript
<script>// JavaScript implementation of lexicographically first// alternate vowel and consonant Stringlet SIZE = 26;// 'ch' is vowel or notfunction isVowel(ch){ if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') { return true; } return false;}// create alternate vowel and consonant String // str1[0...l1-1] and str2[start...l2-1]function createAltStr(str1,str2,start,l){ let finalStr = ""; // first adding character of vowel/consonant // then adding character of consonant/vowel for (let i = 0, j = start; j < l; i++, j++) { finalStr = (finalStr + str1[i]) + str2[j]; } return finalStr;}// function to find the required // lexicographically first alternate // vowel and consonant Stringfunction findAltStr(str){ // hash table to store frequencies // of each character in 'str' let char_freq = new Array(SIZE); // initialize all elements of char_freq[] // to 0 for(let i=0;i<SIZE;i++) char_freq[i]=0; let nv = 0, nc = 0; let vstr = "", cstr = ""; let l = str.length; for (let i = 0; i < l; i++) { let ch = str[i]; // count vowels if (isVowel(ch)) { nv++; } // count consonants else { nc++; } // update frequency of 'ch' in // char_freq[] char_freq[ch.charCodeAt(0) - 97]++; } // no such String can be formed if (Math.abs(nv - nc) >= 2) { return "no such String"; } // form the vowel String 'vstr' and // consonant String 'cstr' which contains // characters in lexicographical order for (let i = 0; i < SIZE; i++) { let ch = String.fromCharCode (i + 97); for (let j = 1; j <= char_freq[i]; j++) { if (isVowel(ch)) { vstr += ch; } else { cstr += ch; } } } // remove first character of vowel String // then create alternate String with // cstr[0...nc-1] and vstr[1...nv-1] if (nv > nc) { return (vstr[0] + createAltStr(cstr, vstr, 1, nv)); } // remove first character of consonant String // then create alternate String with // vstr[0...nv-1] and cstr[1...nc-1] if (nc > nv) { return (cstr[0] + createAltStr(vstr, cstr, 1, nc)); } // if both vowel and consonant // strings are of equal length // start creating String with consonant if (cstr[0] < vstr[0]) { return createAltStr(cstr, vstr, 0, nv); } // start creating String with vowel return createAltStr(vstr, cstr, 0, nc);}// Driver codelet str = "aeroplane";document.write(findAltStr(str));// This code is contributed by rag2127</script> |
Output
alanepero
Time Complexity: O(n), where n is the length of the string.
Auxiliary Space: O(26).
This article is contributed by Ayush Jauhari. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
