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>
Producción
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