You are given a string s consisting of lowercase English characters.
Rearrange only the vowels in the string so that they appear in non-increasing order of their frequency.
If multiple vowels have the same frequency, order them by the position of their first occurrence in s.
Return the modified string.
Vowels are 'a', 'e', 'i', 'o', and 'u'.
The frequency of a letter is the number of times it occurs in the string.
Example 1:
Input: s = "leetcode"
Output: "leetcedo"
Explanation:
['e', 'e', 'o', 'e'] with frequencies: e = 3, o = 1."leetcedo".Example 2:
Input: s = "aeiaaioooa"
Output: "aaaaoooiie"
Explanation:
['a', 'e', 'i', 'a', 'a', 'i', 'o', 'o', 'o', 'a'] with frequencies: a = 4, o = 3, i = 2, e = 1."aaaaoooiie".Example 3:
Input: s = "baeiou"
Output: "baeiou"
Explanation:
Constraints:
1 <= s.length <= 105s consists of lowercase English lettersProblem Overview: You are given a string and need to reorder its vowels based on how frequently they appear. Consonants remain in their original positions while the vowels are rearranged according to their frequency. The challenge is efficiently counting vowels and rebuilding the string in the correct order.
Approach 1: Frequency Map + Sorting (O(n log k) time, O(k) space)
Scan the string once and collect all vowels using a string processing pass. Store their counts in a frequency map using a hash map. Once frequencies are known, convert the vowel keys into a list and sort them by decreasing frequency. Reconstruct the vowel sequence by repeating each vowel based on its count, then iterate through the original string and replace vowel positions sequentially. Sorting is performed on at most k distinct vowels, so the main cost is O(n log k) with O(k) additional space.
Approach 2: Bucket Sort by Frequency (O(n) time, O(n) space)
Instead of sorting vowel keys directly, store frequencies in a map and place vowels into buckets indexed by frequency. Each bucket contains vowels that appear that many times. Since the maximum frequency cannot exceed the string length, the buckets array size is n + 1. Traverse the buckets from highest frequency to lowest and build the ordered vowel list. Finally, iterate through the original string and replace vowels in order. This approach avoids explicit sorting and achieves linear time using a counting-style strategy similar to bucket sorting.
Approach 3: Priority Queue (Max Heap) (O(n log k) time, O(k) space)
Build a frequency map for vowels, then push each vowel and its count into a max heap ordered by frequency. Repeatedly pop the most frequent vowel and append it to the output list the number of times it appears. After generating the sorted vowel sequence, replace vowels in the original string during a second pass. Heap operations cost O(log k), so the overall complexity is O(n log k) with O(k) auxiliary space.
Recommended for interviews: The frequency map plus sorting approach is the most straightforward and typically expected in interviews. It demonstrates understanding of counting with a hash map and controlled sorting. Bucket sort is a good follow‑up optimization showing how to reach linear time when the frequency range is bounded.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Map + Sorting | O(n log k) | O(k) | General solution when using simple counting and sorting logic |
| Bucket Sort by Frequency | O(n) | O(n) | When frequency range is bounded and you want linear time |
| Priority Queue (Max Heap) | O(n log k) | O(k) | Useful when dynamically selecting the most frequent element |
Practice Sort Vowels by Frequency with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor