medium Sort Vowels in a String

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

import java.util.HashMap;

class Solution {

  // Helper method to check if a character is a vowel
  private boolean isVowel(char c) {
    return "aeiouAEIOU".indexOf(c) != -1;
  }

  // Sorts the vowels in a string while maintaining the position of consonants
  public String countingSortVowels(String s) {
    HashMap<Character, Integer> frequencyMap = new HashMap<>();

    // Count each vowel's frequency
    for (char c : s.toCharArray()) {
      if (isVowel(c)) {
        frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
      }
    }

    // Predefined sorted order of vowels based on ASCII values
    String sortedVowelOrder = "AEIOUaeiou";
    StringBuilder result = new StringBuilder();
    int index = 0; // Pointer for sortedVowelOrder

    // Construct the result string with sorted vowels in their positions
    for (char c : s.toCharArray()) {
      if (!isVowel(c)) {
        result.append(c); // Append consonant directly
      } else {
        // Move to the next vowel with remaining count
        while (
          index < sortedVowelOrder.length() &&
          frequencyMap.getOrDefault(sortedVowelOrder.charAt(index), 0) == 0
        ) {
          index++;
        }

        // Check if index is within bounds
        if (index < sortedVowelOrder.length()) {
          result.append(sortedVowelOrder.charAt(index));
          frequencyMap.put(
            sortedVowelOrder.charAt(index),
            frequencyMap.get(sortedVowelOrder.charAt(index)) - 1
          );
        }
      }
    }

    return result.toString();
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.countingSortVowels("gamE")); // gEma
    System.out.println(solution.countingSortVowels("aEiOu")); // Eoaiu
    System.out.println(solution.countingSortVowels("DesIgnGurUs")); // DIsUgnGerus
  }
}

Complexity Analysis

Time Complexity

• Counting Vowels: Traversing the string to count vowel frequencies requires , where (n) is the length of the string.
• Building the Result: Constructing the final string, including searching for the next vowel in the sorted order with a count greater than zero, theoretically could reach , where (m) is the maximum length of the sorted vowel string (sortedVowelOrder). However, since the length of sortedVowelOrder is constant and small (10), the effective complexity for this part remains .
• Overall Time Complexity: Therefore, the total time complexity is since the operations inside the string traversal are bounded by a constant.

Space Complexity

• Frequency Map: The space complexity for the frequency map is since the number of distinct vowels (keys) is constant (10).
• StringBuilder: The space used by the StringBuilder is as it stores the rearranged version of the input string.
• Overall Space Complexity: Thus, the total space complexity of the algorithm is $O(n)S considering the storage required for the result string.