# Sort Vowels in a String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sort-vowels-in-a-string)
Canonical: https://scaleengineer.com/dsa/problems/sort-vowels-in-a-string
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** String
---
## Problem
Given a **0-indexed** string `s`, **permute** `s` to get a new string `t` such that:

* All consonants remain in their original places. More formally, if there is an index `i` with `0 <= i < s.length` such that `s[i]` is a consonant, then `t[i] = s[i]`.
* The vowels must be sorted in the **nondecreasing** order of their **ASCII** values. More formally, for pairs of indices `i`, `j` with `0 <= i < j < s.length` such that `s[i]` and `s[j]` are vowels, then `t[i]` must not have a higher ASCII value than `t[j]`.

Return _the resulting string_.

The vowels are `'a'`, `'e'`, `'i'`, `'o'`, and `'u'`, and they can appear in lowercase or uppercase. Consonants comprise all letters that are not vowels.

**Example 1:**

**Input:** s = "lEetcOde"
**Output:** "lEOtcede"
**Explanation:** 'E', 'O', and 'e' are the vowels in s; 'l', 't', 'c', and 'd' are all consonants. The vowels are sorted according to their ASCII values, and the consonants remain in the same places.

**Example 2:**

**Input:** s = "lYmpH"
**Output:** "lYmpH"
**Explanation:** There are no vowels in s (all characters in s are consonants), so we return "lYmpH".

**Constraints:**

* `1 <= s.length <= 105`
* `s` consists only of letters of the English alphabet in **uppercase and lowercase**.

# Approaches
## Two-Pass with List and Sorting
This approach involves two main passes over the string's data. In the first pass, we identify and collect all the vowels into a separate list. In the second pass, after sorting this list of vowels, we iterate through the original string's positions again and replace the vowel positions with the sorted vowels.
**Time:** O(N + k log k), where N is the length of the string and k is the number of vowels. The first loop to collect vowels takes O(N) time. Sorting the list of k vowels takes O(k log k) time. The second loop to place the sorted vowels takes O(N) time. In the worst case, where all characters are vowels (k ≈ N), the complexity is O(N log N). · **Space:** O(N), where N is the length of the string. We use a list to store the k vowels, which takes O(k) space (where k is the number of vowels). We also use a character array to build the result string, which takes O(N) space. Therefore, the total space complexity is O(k + N), which simplifies to O(N).
**Pros:** Relatively straightforward to understand and implement.; Leverages standard library sorting functions, leading to concise code.
**Cons:** The time complexity is dominated by the sorting step, which is not optimal for this problem's constraints as there is a limited set of characters to sort.
### Explanation
The core idea is to separate the problem into two parts: handling vowels and handling consonants. Since consonants must remain in their original places, we only need to focus on the vowels. We can extract all vowels from the string, sort them independently, and then place them back into the positions that were originally occupied by vowels.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    private boolean isVowel(char c) {
        return "aeiouAEIOU".indexOf(c) != -1;
    }

    public String sortVowels(String s) {
        List<Character> vowels = new ArrayList<>();
        for (char c : s.toCharArray()) {
            if (isVowel(c)) {
                vowels.add(c);
            }
        }

        // Sort the collected vowels. Time complexity: O(k log k)
        Collections.sort(vowels);

        char[] resultChars = s.toCharArray();
        int vowelIndex = 0;
        for (int i = 0; i < s.length(); i++) {
            if (isVowel(s.charAt(i))) {
                resultChars[i] = vowels.get(vowelIndex++);
            }
        }

        return new String(resultChars);
    }
}
```
### Algorithm
- Create a helper function `isVowel(char c)` to check if a character is a vowel.
- Initialize an empty list, `vowels`, to store characters.
- Iterate through the input string `s`. If a character `c` is a vowel, add it to the `vowels` list.
- Sort the `vowels` list. In Java, `Collections.sort()` can be used, which has a time complexity of O(k log k) where k is the number of vowels.
- Convert the input string `s` to a character array, `resultChars`.
- Initialize an index `vowelIndex = 0` to point to the current vowel in the sorted list.
- Iterate through the string `s` with index `i` from 0 to `s.length() - 1`.
- If the character `s.charAt(i)` is a vowel, replace the character at `resultChars[i]` with the vowel from `vowels.get(vowelIndex)` and increment `vowelIndex`.
- Convert the `resultChars` array back to a string and return it.

## Two-Pass with Counting Sort
A more efficient approach utilizes counting sort, as the set of characters to be sorted (vowels) is small and fixed. We can count the frequency of each vowel, then reconstruct the sorted sequence of vowels, and finally place them back into the original string's vowel positions. This avoids a comparison-based sort and achieves linear time complexity.
**Time:** O(N), where N is the length of the string. The first pass to count vowel frequencies takes O(N). Building the sorted vowel string takes constant time with respect to N, as we iterate through a fixed set of 10 vowels (O(1)) and append k total vowels (O(k)). The final pass to construct the result string takes O(N). The overall complexity is linear, O(N + k), which is O(N). · **Space:** O(N). The `vowelCounts` array takes constant space, O(1), as its size is fixed. The `sortedVowels` `StringBuilder` stores k vowels, taking O(k) space. The final `resultChars` array takes O(N) space. The total space complexity is O(1 + k + N), which simplifies to O(N).
**Pros:** Optimal time complexity of O(N).; Highly efficient for large inputs as it avoids a comparison-based sort.
**Cons:** Slightly more complex logic for counting and rebuilding the sorted vowel sequence compared to using a generic sort.
### Explanation
Since the number of unique vowels is constant (10), we can use a counting-based sorting method instead of a general-purpose comparison sort like MergeSort or QuickSort. This is significantly faster. We first count the occurrences of each vowel. Then, we build a new string containing all the vowels, sorted by ASCII value, by appending each vowel character according to its count and the predefined ASCII order. Finally, we iterate through the original string one last time, replacing the vowel placeholders with the characters from our sorted vowel string.

```java
class Solution {
    private boolean isVowel(char c) {
        return "aeiouAEIOU".indexOf(c) != -1;
    }

    public String sortVowels(String s) {
        // Step 1: Count the frequency of each vowel.
        int[] vowelCounts = new int[128]; // ASCII size is sufficient.
        for (char c : s.toCharArray()) {
            if (isVowel(c)) {
                vowelCounts[c]++;
            }
        }

        // Step 2: Create a string of sorted vowels.
        String sortedVowelChars = "AEIOUaeiou";
        StringBuilder sortedVowels = new StringBuilder();
        for (char vowel : sortedVowelChars.toCharArray()) {
            for (int i = 0; i < vowelCounts[vowel]; i++) {
                sortedVowels.append(vowel);
            }
        }

        // Step 3: Place the sorted vowels back into the string.
        char[] resultChars = s.toCharArray();
        int vowelIndex = 0;
        for (int i = 0; i < s.length(); i++) {
            if (isVowel(s.charAt(i))) {
                resultChars[i] = sortedVowels.charAt(vowelIndex++);
            }
        }

        return new String(resultChars);
    }
}
```
### Algorithm
- Create a frequency map to store the counts of each vowel. An array of size 128 (for ASCII characters) is a simple and efficient way to implement this.
- Iterate through the input string `s`. For each character, if it's a vowel, increment its count in the frequency array.
- Create a sorted string or list of all vowels. This can be done by iterating through the possible vowels in their ASCII-sorted order (e.g., 'A', 'E', 'I', 'O', 'U', 'a', 'e', 'i', 'o', 'u'). For each vowel, append it to a `StringBuilder`, say `sortedVowels`, as many times as its count in the frequency array.
- Convert the input string `s` to a character array, `resultChars`.
- Initialize a pointer, `vowelIndex = 0`, for the `sortedVowels` string.
- Iterate through the `resultChars` array from `i = 0` to `s.length() - 1`.
- If the original character `s.charAt(i)` was a vowel, replace `resultChars[i]` with the character from `sortedVowels.charAt(vowelIndex)` and increment `vowelIndex`.
- Finally, create a new string from `resultChars` and return it.

# Solutions
### CSharp

```csharp
public class Solution {
    public string SortVowels(string s) {
        List < char > vs = new List < char > ();
        char[] cs = s.ToCharArray();
        foreach(char c in cs) {
            if (IsVowel(c)) {
                vs.Add(c);
            }
        }
        vs.Sort();
        for (int i = 0, j = 0; i < cs.Length; ++i) {
            if (IsVowel(cs[i])) {
                cs[i] = vs[j++];
            }
        }
        return new string(cs);
    }
    public bool IsVowel(char c) {
        c = char.ToLower(c);
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}
```

### Java

```java
class Solution { public String sortVowels ( String s ) { List < Character > vs = new ArrayList <>(); char [] cs = s . toCharArray (); for ( char c : cs ) { char d = Character . toLowerCase ( c ); if ( d == 'a' || d == 'e' || d == 'i' || d == 'o' || d == 'u' ) { vs . add ( c ); } } Collections . sort ( vs ); for ( int i = 0 , j = 0 ; i < cs . length ; ++ i ) { char d = Character . toLowerCase ( cs [ i ]); if ( d == 'a' || d == 'e' || d == 'i' || d == 'o' || d == 'u' ) { cs [ i ] = vs . get ( j ++); } } return String . valueOf ( cs ); } }
```

### CPP

```cpp
class Solution { public: string sortVowels ( string s ) { string vs ; for ( auto c : s ) { char d = tolower ( c ); if ( d == 'a' || d == 'e' || d == 'i' || d == 'o' || d == 'u' ) { vs . push_back ( c ); } } sort ( vs . begin (), vs . end ()); for ( int i = 0 , j = 0 ; i < s . size (); ++ i ) { char d = tolower ( s [ i ]); if ( d == 'a' || d == 'e' || d == 'i' || d == 'o' || d == 'u' ) { s [ i ] = vs [ j ++ ]; } } return s ; } };
```

### Python

```python
class Solution : def sortVowels ( self , s : str ) -> str : vs = [ c for c in s if c . lower () in "aeiou" ] vs . sort () cs = list ( s ) j = 0 for i , c in enumerate ( cs ): if c . lower () in "aeiou" : cs [ i ] = vs [ j ] j += 1 return "" . join ( cs )
```