Dada una string str . El problema es reorganizar los caracteres de la string dada de modo que las vocales y las consonantes ocupen posiciones alternas y la string así formada sea lexicográficamente (alfabéticamente) la más pequeña. Si la string no se puede reorganizar de la forma deseada, imprima «no such string».
Ejemplos:
Input : mango Output : gamon It could be arranged in other ways too, like manog, etc., but gamon is lexicographically smallest. Input : aeroplane Output : alanepero
Enfoque: Los siguientes son los pasos:
- Almacene la frecuencia de cada carácter de la string de entrada en una tabla hash.
- Cuente el número de vocales y consonantes en una string dada.
- Si la diferencia entre los conteos es más de uno, devuelve «No es posible».
- De lo contrario, forme strings separadas de vocales y consonantes con la ayuda de la tabla hash que tenga frecuencias de cada carácter de la string de entrada. Tenga en cuenta que, al crear strings de vocales y consonantes, los caracteres de las strings respectivas deben estar en orden alfabético.
- Si hay más vocales que consonantes, imprima primero la primera vocal y luego imprima los caracteres restantes de las strings de consonantes y vocales alternativamente.
- Si hay más consonantes que vocales, imprima primero la consonante primero y luego imprima los caracteres restantes de las strings de vocales y consonantes alternativamente.
- Si el número es el mismo, compare la primera vocal con la primera consonante e imprima primero la más pequeña y luego continúe imprimiendo alternativamente.
Implementación:
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 not 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] 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 string string 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 above int 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 string SIZE = 26 # 'ch' is vowel or not def 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 string def 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 Code if __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 contributed by PrinciRaj1992*/
Javascript
<script> // JavaScript implementation of lexicographically first // alternate vowel and consonant String let SIZE = 26; // 'ch' is vowel or not function 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 String function 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 code let str = "aeroplane"; document.write(findAltStr(str)); // This code is contributed by rag2127 </script>
alanepero
Complejidad de tiempo: O(n) , donde n es la longitud de la string.
Espacio Auxiliar: O(26).
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA