Problem Statement

Given a string s, return an updated string t such that all consonants in the string s stay in their original positions while any vowels in the string are reordered according to their ASCII values.

The vowels are 'A', 'E', 'I', 'O', and 'U'. These vowels can appear in lowercase or uppercase. All other letters except vowels are consonants.

Examples

• Example 1:

  • Input: "gamE"
  • Expected Output: "gEma"
  • Justification: The vowels in "gamE" are 'a' and 'E'. Sorting these by ASCII values, 'E' comes before 'a'. Hence, they are placed in the order 'E', 'a' in the output, while consonants remain unchanged.

• Example 2:

  • Input: "aEiOu"
  • Expected Output: "EOaiu"
  • Justification: The input consists only of vowels. When we sort them according to their ASCII values, the uppercase vowels come first and then the lowercase vowel comes in 'aiou' order.

• Example 3:

  • Input: "DesIgnGurUs"
  • Expected Output: "DIsUgnGerus"
  • Justification: The vowels in "DesIgnGurUs" string are 'e', 'I', 'u', and 'U'. Their order according to ASCII value is 'I', 'U', 'e' and 'u'.

Constraints:

• 1 <= s.length <= 10⁵
• s consists only of letters of the English alphabet in uppercase and lowercase.

Solution

To solve the problem, we will use the counting sort approach. For that, we'll first identify and count the frequency of each vowel in the input string. This is done using a hash map that maps vowels to their frequencies. After counting, we create a sorted sequence of vowels (both uppercase and lowercase) to act as a guide for reinserting vowels into the string in sorted order. As we reconstruct the string, we replace each vowel with the next vowel in the predefined sorted sequence, ensuring that each vowel is used exactly as many times as it appears in the input string.

This method leverages the fixed number of vowel types (10 in total) to sort and replace vowels efficiently, guaranteeing that the operation stays within a linear time complexity relative to the size of the input string.

Step-by-step Algorithm

1. Initialize Data Structures:

   • A HashMap named frequencyMap to store the count of each vowel.
   • A StringBuilder named result to construct the final string.

2. Count Vowels:

   • Iterate through each character in the input string.
   • If the character is a vowel (checked using the isVowel method), increment its count in frequencyMap.

3. Prepare for Reinsertion:

   • Define a string sortedVowelOrder containing all possible vowels sorted by ASCII values: "AEIOUaeiou".

4. Reconstruct the String:

   • Initialize an index pointer index set to 0, to track the current position in sortedVowelOrder.
   • Iterate through each character of the input string again.
   • If the character is not a vowel, append it directly to result.
   • If it is a vowel, find the next vowel in sortedVowelOrder with a remaining count (using index to check frequencyMap).
   • Append this vowel to result and decrement its count in frequencyMap.

Algorithm Walkthrough

Input: "DesIgnGurUs"

Detailed Steps:

1. Counting Vowels:

   • D, s, g, n, G, r, s are consonants and are ignored in counting.
   • e, I, u, U are vowels.
   • After iterating through the string, frequencyMap looks like this:
     • e: 1
     • I: 1
     • u: 1
     • U: 1

2. Sorted Vowel Order: "AEIOUaeiou"

3. Reconstructing the String:

   • Start with an empty result.
   • Characters: D, s, I, g, n, G, r, U, s are processed directly if consonants.
   • For vowels:
     • First vowel is 'e', find the smallest unused vowel from sortedVowelOrder, which is 'I' (since 'A', 'E' are not present, 'I' is the first with a non-zero count).
     • Replace 'e' with 'I'.
     • Next vowel is 'I', proceed in sortedVowelOrder to 'U' as the next vowel with a non-zero count.
     • Next, 'u' is replaced by 'e', which is the next in sorted order.
     • Lastly, 'U' remains and is replaced by 'u' (the next and only remaining vowel with a non-zero count).
   • The final result is constructed: "DIsUgnGerus".

Code