Skip to main content
Talentd

Sort Vowels by Frequency - Solution & Explanation

MediumStringSortingCounting9 min read
Practice this problem

Problem Statement

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:​​​​​​​

  • Vowels in the string are ['e', 'e', 'o', 'e'] with frequencies: e = 3, o = 1.
  • Sorting in non-increasing order of frequency and placing them back into the vowel positions results in "leetcedo".

Example 2:

Input: s = "aeiaaioooa"

Output: "aaaaoooiie"

Explanation:​​​​​​​

  • Vowels in the string are ['a', 'e', 'i', 'a', 'a', 'i', 'o', 'o', 'o', 'a'] with frequencies: a = 4, o = 3, i = 2, e = 1.
  • Sorting them in non-increasing order of frequency and placing them back into the vowel positions results in "aaaaoooiie".

Example 3:

Input: s = "baeiou"

Output: "baeiou"

Explanation:

  • Each vowel appears exactly once, so all have the same frequency.
  • Thus, they retain their relative order based on first occurrence, and the string remains unchanged.

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters

Approach Overview

Problem 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.

Solution

We can use a hash table cnt to record the frequency of each vowel. We also need a list vowels to store the vowels that appear in the string, ordered by their first occurrence.

We then sort the vowels list with a custom comparator: vowels are sorted in non-increasing order of their frequency.

Finally, we traverse the string, replacing each vowel with the corresponding letter from the vowels list, and update the frequency in the hash table. When the frequency of a vowel becomes 0, we move the pointer in the vowels list forward by one.

The time complexity is O(n + |\Sigma| log |\Sigma|) and the space complexity is O(n + |\Sigma|), where n is the length of the string and \Sigma is the set of vowels that appear in the string.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Frequency Map + SortingO(n log k)O(k)General solution when using simple counting and sorting logic
Bucket Sort by FrequencyO(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

Video Solution

Sort Vowels by Frequency | LeetCode 3913 | Weekly Contest 499 | Java Code | Developer Coder • Developer Coder • 207 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sort Vowels by Frequency easy or hard?
The problem is typically rated Medium because it combines multiple concepts: identifying vowels, counting frequencies, sorting or bucket grouping, and reconstructing the string. The individual operations are simple, but combining them efficiently requires careful implementation.
Sort Vowels by Frequency Python/Java solution
Implement the solution by scanning the string, storing vowel counts in a dictionary (Python) or HashMap (Java), sorting vowels by frequency, and rebuilding the result. Replace vowels during a second pass through the string to maintain consonant positions.
How to solve Sort Vowels by Frequency in O(n)?
Use a bucket sort strategy. First count vowel frequencies with a hash map, then place vowels into buckets indexed by their frequency. Traverse buckets from highest frequency to lowest to build the sorted vowel list, then replace vowels during a second pass of the string. This avoids comparison sorting and runs in linear time.
What is the best approach for Sort Vowels by Frequency?
The most practical approach uses a hash map to count vowel frequencies and then sorts the vowels based on their counts. After sorting, rebuild the vowel sequence and place it back into the original string positions. This solution runs in O(n log k) time where k is the number of distinct vowels and uses O(k) extra space.
Is Sort Vowels by Frequency asked at Google/Amazon/Meta?
Frequency counting and character reordering problems appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem name may vary, interviewers often test string manipulation combined with hash maps and sorting patterns.
What data structure is used in Sort Vowels by Frequency?
The main data structure is a hash map for counting vowel frequencies. Depending on the approach, the solution may also use a sorting array, a bucket array for frequency grouping, or a priority queue (max heap) to retrieve vowels in descending frequency order.
What is the time complexity of Sort Vowels by Frequency?
The common solution runs in O(n log k) time due to sorting the distinct vowels after counting frequencies. Counting vowels requires O(n) time and sorting at most k vowel types adds the log factor. A bucket sort variant can reduce this to O(n) time when frequencies are bounded by the string length.

Ready to solve this problem?

Practice Sort Vowels by Frequency with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring