Alternate Vowel and Consonant string in Java
A string is provided to us. The task is to arrange its characters in a manner where the vowels and consonants are placed alternately. If it is not feasible to rearrange the string as desired, display the message "no such string." It is crucial to preserve the order of vowels and consonants among themselves. If there are several possible rearrangements, output the lexicographically smaller one.
Example 1:
Input:
String s = "aeroplane"
Output:
The string after alternating vowel and consonant is arepolane.
Explanation:
In the string "aeroplane" there are 5 vowels and 4 consonants. Now, the difference between the vowels and consonants is 1. Since the number of vowels is greater, the first vowel is printed as it is, and then it recurs the remaining string. Now, the remaining string is taken and follows the same procedure. Finally, the output is printed as arepolane.
Example 2:
Input:
String s = "onse"
Output:
The string after alternating vowels and consonants is the nose.
Explanation:
In the string "onse" there are 2 vowels and 2 consonants. Now, the difference between the vowels and consonants is 0. Since the number of vowels and the number of consonants is the same, it compares the first vowel with the first consonant, and the least number is printed first. Hence, the output is printed as a nose.
Example 3:
Input:
String s = "mississippi"
Output:
The string cannot be rearranged, and no such string exists.
Explanation:
In the string "mississippi" there are 4 vowels and 7 consonants. Now, the difference between the vowels and consonants is 3. Since the difference is greater than 1. Hence, there is no such string printed.
Approach: Using Recursion
Step 1: Count the number of consonants and vowels in the provided string.
Step 2: Return "No such string " if there is more than one count difference.
Step 3: Print the first vowel first and repeat for the rest of the string if there are more vowels than consonants.
Step 4: Print the first consonant and then repeat for the rest of the string if there are more consonants than vowels.
Step 5: Compare the first vowel with the first consonant. If the counts are the same, then print the smaller one first.
Implementation:
FileName: AlternateVandCRecursion.java
import java.util.*;
import java.io.*;
public class AlternateVandCRecursion
{
// if character 'c' is a vowel or not
static boolean Vowel(char c)
{
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c =='u')
return true;
return false;
}
// create a string of alternating consonants and vowels.
// s1[0...l1-1] and s2[s...l2-1]
static String createAltStr(String s1, String s2, int s, int l)
{
String finalStr = "";
// put the vowel/consonant character first,
// then the consonant/vowel character afterwards
for (int i = 0, j = s; j < l; i++, j++)
finalStr = (finalStr + s1.charAt(i)) + s2.charAt(j);
return finalStr;
}
// Vowel and consonant strings are alternated
// in this function to determine the necessary
static String findAltStr(String str)
{
int nvowels = 0, nconsonants = 0;
String vowelstr = "", consonantstr = "";
int l = str.length();
for (int i = 0; i < l; i++)
{
char c = str.charAt(i);
//Update the vowel string and count the vowels
if (Vowel(c))
{
nvowels++;
vowelstr = vowelstr + c;
}
// update the consonants string and count the consonants
else
{
nconsonants++;
consonantstr = consonantstr + c;
}
}
// no Such a string cannot be created.
if (Math.abs(nvowels - nconsonants) >= 2)
return "no such string";
// cut off the vowel string's first character
//Then make an alternate string with
// consonantstr[0...nconsonants-1] and vowelstr[1...nvowel-1]
if (nvowels > nconsonants)
return (vowelstr.charAt(0) + createAltStr(consonantstr, vowelstr, 1, nvowels));
//Remove the consonant string's first character,
//Then make an alternate string with
// vowelstr[0...nvowels-1] and consonantstr[1...nconsonants-1]
if (nconsonants > nvowels)
return (consonantstr.charAt(0) + createAltStr(vowelstr, consonantstr, 1, nconsonants));
//Start creating the string with the consonant
// if the vowel and consonant strings are of equal length.
if (consonantstr.charAt(0) < vowelstr.charAt(0))
return createAltStr(consonantstr, vowelstr, 0, nvowels);
//Begin string creation with vowels
return createAltStr(vowelstr, consonantstr, 0, nconsonants);
}
public static void main(String args[])
{
String str = "aeroplane";
System.out.println("The string after alternating vowel and consonant is " + findAltStr(str));
}
}
Output:
The string after alternating vowel and consonant is arepolane
Complexity Analysis:
The time complexity of the above program is O(N), and the space complexity is O(N), where N represents the Length of the String.
Approach: By Hashing
Algorithm:
Step 1: Declare variables vow and con to store the count of vowels and consonants, and vectors p1 and p2 to store the occurrence.
Step 2: Increase the number of vowels and consonants that occur in the hash table as you iterate through the string.
Step 3: We will return "no such string" if the absolute difference between vow and con is larger than 1. In this scenario, a string with an alternate vowel and consonant is not conceivable.
Step 4: To iterate through the vector and identify the first vowel and consonants, declare the variables iterate1, iterate2, and i.
Step 5: We shall increase the first iterator while iterate1<p1.size() and p1[iterate1] = 0.
Step 6: We will increase the second iterator while iterate2<p2.size() and p2[iterate2] = 0.
Step 7: Declare a Boolean function to store whether a consonant is greater than a vowel and to determine which will come first, the consonant or the vowel.
Step 8: If vow and con are equal, then f=iterate1>iterate2 (smaller in lexicography).
Step 9: Given that i is less than n and that iterate1 and iterate2 are smaller than p1.size() and p2.size(), respectively:
Step 9.1: Iterate through p2 until p2[iterate2] equals zero, then increment iterate2 and set f=false if s[i]=iterate2+'a', – p2[iterate2].
Step 9.2: If p1[iterate1] is equal to zero, iterate through p1 and increment iterate1, f=true. Else, s[i]=iterate1+'a', – p1[iterate1], and increase in i.
Step 10: Look for situations in which there is just one vowel or consonant remaining.
Step 11: Give the string back.
Implementation:
FileName: HashingAlternateVandC.java
import java.util.*;
import java.io.*;
public class HashingAlternateVandC
{
static String AlterateVandC(String str)
{
char[] s = str.toCharArray();
int n = s.length;
int[] p1 = new int[26];
int[] p2 = new int[26]; // to save consonants and vowels
int vow = 0, con = 0;
for (char ch : s)
{
if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
{
// if the character is a vowel
p1[ch - 'a']++;
vow++;
}
else
{
// is the character is a consonant
p2[ch - 'a']++;
con++;
}
}
if (Math.abs(vow - con) > 1)
return "no such string";
// if the difference between them is more than one,
// a string with an alternate vowel and a consonant cannot be created.
int iterate1 = 0, iterate2 = 0, i = 0;
while (iterate1 < p1.length && p1[iterate1] == 0)
iterate1++; // to determine the first vowel
while (iterate2 < p2.length && p2[iterate2] == 0)
iterate2++; // to determine the first consonant
boolean f = con > vow;
// if there are more consonants,
//We shall arrange them consonants first, else vowel
if (vow == con)
{
f = iterate1 > iterate2;
// determine which is lexiographically smaller if they are equal.
}
while ((iterate1 < p1.length && iterate2 < p2.length) && i < n)
{
if (f)
{
s[i] = (char)(iterate2 + 'a');
--p2[iterate2];
while (iterate2 < p2.length && p2[iterate2] == 0)
iterate2++;
f = false;
//This will cause the following vowel to be placed.
}
else
{
s[i] = (char)(iterate1 + 'a');
--p1[iterate1];
while (iterate1 < p1.length && p1[iterate1] == 0)
iterate1++;
f = true;
//This will cause the following consonant to be placed.
}
++i;
}
if (iterate1 != p1.length)
s[i] = (char)(iterate1 + 'a'); // if one vowel is still there
else if (iterate2 != p2.length)
s[i] = (char)(iterate2 + 'a'); // if one consonant is still there
return String.valueOf(s);
}
public static void main(String[] args)
{
String str = "mississipi";
System.out.println("The string after alternating vowel and consonant is " + AlterateVandC(str));
}
}
Output:
The string after alternating vowel and consonant is no such string
Complexity Analysis:
The time complexity of the above program is O(N), and the space complexity is O(N), where N represents the Length of the String.