Facebook Pixel

3913. Sort Vowels by Frequency

Medium
LeetCode ↗
ProblemPatternIdeaExampleCodeComplexPitfalls

Problem Description

You are given a string s consisting of lowercase English characters.

Your task is to rearrange only the vowels in the string so that they appear in non-increasing order of their frequency. The non-vowel characters must stay in their original positions, and only the positions originally occupied by vowels can be filled with the rearranged vowels.

The frequency of a letter is the number of times it occurs in the string. When multiple vowels share the same frequency, you should order them by the position of their first occurrence in s (the vowel that appears earlier comes first).

After rearranging, return the modified string.

The vowels are 'a', 'e', 'i', 'o', and 'u'.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

Linkedlist?noFastlookup orcounting?yesHash Table /Counting

Counting character or element frequencies with a hash map enables the solution.

Open in Flowchart

Intuition

The key observation is that only the vowels need to be rearranged, while every other character stays exactly where it is. This means we can separate the problem into two parts: figuring out the correct order of the vowels, and then placing them back into the positions that originally held vowels.

To decide the order, we need two pieces of information for each vowel: its frequency (how many times it appears) and the position of its first occurrence (used as a tiebreaker). We can gather both in a single pass through the string. By using a counter to track frequencies and appending each vowel to a list the first time we see it, the list naturally records the vowels in the order of their first appearance.

Once we have these, sorting becomes straightforward. We sort the list of distinct vowels by frequency in non-increasing order. Since Python's sort is stable, vowels with the same frequency automatically retain the order in which they were first added — which is exactly the first-occurrence tiebreaker we want.

The final step is to rebuild the string. We walk through s again, and whenever we hit a vowel position, we fill it with the current vowel from our sorted list. We decrement that vowel's remaining count, and once a vowel has been fully used up (its count reaches 0), we advance to the next vowel in the sorted list. Non-vowel characters are left untouched. This guarantees the most frequent vowels fill the earliest vowel slots, producing the desired arrangement.

Solution Approach

Solution 1: Counting + Custom Sorting

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

Step 1: Collect vowels and count frequencies.

We define a set st = set("aeiou") for quick vowel lookups. Then we traverse the string s once:

  • If the character is not a vowel, we skip it.
  • If the character is a vowel we haven't seen before (c not in cnt), we append it to the vowels list. Because we only append on the first sighting, vowels ends up ordered by each vowel's first occurrence.
  • In all vowel cases, we increment cnt[c].

Step 2: Sort the vowels by frequency.

We sort the vowels list with the custom key lambda c: -cnt[c], which arranges vowels in non-increasing order of frequency. Since Python's sort is stable, vowels with equal frequency keep their original order in the list — exactly the first-occurrence tiebreaker required.

Step 3: Rebuild the string.

We convert s into a list ans so we can modify characters in place, and use a pointer i into the sorted vowels list. Traversing s again:

  • Non-vowel positions are left as they are.
  • At each vowel position k, we assign ans[k] the current vowel vowels[i], then decrement its remaining count with cnt[c] -= 1.
  • When a vowel's count reaches 0, it has been fully placed, so we advance the pointer with i += 1 to move on to the next vowel.

Finally, we return "".join(ans) to produce the result.

Complexity Analysis:

  • Time complexity: O(n), where n is the length of the string. We make two passes over s, and the sort only handles at most 5 vowels, which is constant.
  • Space complexity: O(n) for the ans list. The cnt table and vowels list use only O(1) extra space since there are at most 5 distinct vowels.

Example Walkthrough

Let's trace through the solution using the example string s = "leetcode".

Setup: The vowels we care about are {'a', 'e', 'i', 'o', 'u'}. In "leetcode", the vowel positions are:

index:  0   1   2   3   4   5   6   7
char:   l   e   e   t   c   o   d   e
              ↑   ↑           ↑       ↑
            vowel vowel     vowel   vowel

So vowels appear at indices 1, 2, 5, 7.

Step 1: Collect vowels and count frequencies.

We walk through s once, maintaining cnt (frequencies) and vowels (distinct vowels by first occurrence):

indexcharvowel?actioncntvowels
0lnoskip{}[]
1eyesnew → append, count{e:1}[e]
2eyesseen → count{e:2}[e]
3tnoskip{e:2}[e]
4cnoskip{e:2}[e]
5oyesnew → append, count{e:2, o:1}[e, o]
6dnoskip{e:2, o:1}[e, o]
7eyesseen → count{e:3, o:1}[e, o]

After this pass:

  • cnt = {e: 3, o: 1}
  • vowels = [e, o] (ordered by first occurrence)

Step 2: Sort the vowels by frequency.

Sort vowels using the key lambda c: -cnt[c]:

  • e has frequency 3 → key -3
  • o has frequency 1 → key -1

Since -3 < -1, e comes first:

vowels = [e, o]   (already in correct non-increasing order)

Step 3: Rebuild the string.

Convert to ans = ['l','e','e','t','c','o','d','e'], pointer i = 0. We walk through s again, filling only vowel positions from vowels:

indexcharvowel?placecnt afteri
0lnoleave l—0
1eyesans[1]=e, cnt[e]→2{e:2,o:1}0
2eyesans[2]=e, cnt[e]→1{e:1,o:1}0
3tnoleave t—0
4cnoleave c—0
5oyesans[5]=e, cnt[e]→0 → advance i{e:0,o:1}1
6dnoleave d—1
7eyesans[7]=o, cnt[o]→0 → advance i{e:0,o:0}2

The three e's (most frequent) fill the first three vowel slots (indices 1, 2, 5), and the single o fills the last vowel slot (index 7).

Result:

ans = ['l','e','e','t','c','e','d','o']

Joining gives "leetcedo". Notice that the non-vowel characters (l, t, c, d) never moved, and only the vowel positions were reassigned according to descending frequency.

Solution Implementation

1from collections import Counter
2
3
4class Solution:
5    def sortVowels(self, s: str) -> str:
6        # Set of all vowels (both lowercase and uppercase)
7        vowel_set = set("aeiouAEIOU")
8
9        # Count the occurrences of each vowel and collect distinct vowels
10        counter = Counter()
11        distinct_vowels = []
12        for char in s:
13            if char not in vowel_set:
14                continue
15            if char not in counter:
16                distinct_vowels.append(char)
17            counter[char] += 1
18
19        # Sort distinct vowels by ASCII value (nondecreasing order)
20        distinct_vowels.sort()
21
22        # Rebuild the string, placing sorted vowels back into vowel positions
23        result = list(s)
24        index = 0  # pointer into distinct_vowels
25        for pos, char in enumerate(s):
26            if char not in vowel_set:
27                continue
28            # Assign the current smallest available vowel
29            current = distinct_vowels[index]
30            result[pos] = current
31            counter[current] -= 1
32            # Move to the next distinct vowel once the current one is exhausted
33            if counter[current] == 0:
34                index += 1
35
36        return "".join(result)
37```
38
39**Key changes explained:**
40
41- **Vowel set**: Expanded to `"aeiouAEIOU"` so uppercase vowels are also recognized and sorted.
42- **Sort order**: Changed `sort(key=lambda c: -cnt[c])` to a plain `sort()`. Since ASCII ordering is required, and uppercase letters (`A`–`U`) have smaller ASCII values than lowercase letters (`a`–`u`), this naturally produces the correct nondecreasing order.
43- **Naming**: `st` → `vowel_set`, `cnt` → `counter`, `vowels` → `distinct_vowels`, `i` → `index`, loop variables clarified (`pos`, `char`, `current`).
44- **Import**: Added `from collections import Counter`.
45
46**Alternative perspective** — a simpler, equally valid solution collects all vowels, sorts them, and refills using a single pointer (no need for a counter):
47
48```python3
49class Solution:
50    def sortVowels(self, s: str) -> str:
51        vowel_set = set("aeiouAEIOU")
52        # Gather and sort every vowel by ASCII value
53        sorted_vowels = sorted(c for c in s if c in vowel_set)
54        result = list(s)
55        index = 0
56        for pos, char in enumerate(s):
57            if char in vowel_set:
58                result[pos] = sorted_vowels[index]
59                index += 1
60        return "".join(result)
61
1class Solution {
2    public String sortVowels(String s) {
3        // Set of vowels (both lowercase and uppercase) for quick membership checks.
4        Set<Character> vowelSet = Set.of(
5            'a', 'e', 'i', 'o', 'u',
6            'A', 'E', 'I', 'O', 'U'
7        );
8
9        // Distinct vowels encountered, later sorted by ASCII value.
10        List<Character> distinctVowels = new ArrayList<>();
11        // Frequency of each vowel in the input string.
12        Map<Character, Integer> vowelCount = new HashMap<>();
13
14        // First pass: collect every vowel and tally its occurrences.
15        for (char c : s.toCharArray()) {
16            if (!vowelSet.contains(c)) {
17                continue;
18            }
19            // Record the vowel only the first time it appears.
20            if (!vowelCount.containsKey(c)) {
21                distinctVowels.add(c);
22            }
23            vowelCount.merge(c, 1, Integer::sum);
24        }
25
26        // Sort distinct vowels in nondecreasing ASCII order
27        // (uppercase letters come before lowercase ones in ASCII).
28        distinctVowels.sort((a, b) -> a - b);
29
30        char[] result = s.toCharArray();
31        int vowelIndex = 0; // Pointer into the sorted distinct vowels.
32
33        // Second pass: refill every vowel position in sorted order,
34        // exhausting one vowel's count before moving to the next.
35        for (int pos = 0; pos < s.length(); pos++) {
36            char c = s.charAt(pos);
37            // Leave consonants and other characters untouched.
38            if (!vowelSet.contains(c)) {
39                continue;
40            }
41            char current = distinctVowels.get(vowelIndex);
42            result[pos] = current;
43            // Decrease the remaining count for the placed vowel.
44            vowelCount.merge(current, -1, Integer::sum);
45            // Once the current vowel is used up, advance to the next.
46            if (vowelCount.get(current) == 0) {
47                vowelIndex++;
48            }
49        }
50
51        return new String(result);
52    }
53}
54```
55
56**Key points and reasoning:**
57
58- **The only structural change** from your original is `distinctVowels.sort((a, b) -> a - b)` (ascending ASCII) instead of sorting by count. This makes the output correct per the problem requirements.
59- **Counting-bucket strategy**: Instead of building a full sorted array of all vowels, this keeps just the distinct vowels plus their counts. The second pass walks through sorted distinct vowels, placing each as many times as its count before advancing `vowelIndex`. This is functionally equivalent to sorting all vowels but uses less per-character sorting.
60- **Why uppercase matters**: In ASCII, `'A'`(65) < `'a'`(97), so uppercase vowels naturally sort before lowercase ones with the `a - b` comparator—matching the expected ordering.
61
62**Alternative perspective (simpler, more idiomatic):**
63
64If clarity over micro-optimization is preferred, extracting all vowels into a list, sorting them directly, then writing back is more straightforward:
65
66```java
67class Solution {
68    public String sortVowels(String s) {
69        Set<Character> vowelSet = Set.of(
70            'a', 'e', 'i', 'o', 'u',
71            'A', 'E', 'I', 'O', 'U'
72        );
73
74        // Gather all vowels in the order they appear.
75        List<Character> vowels = new ArrayList<>();
76        for (char c : s.toCharArray()) {
77            if (vowelSet.contains(c)) {
78                vowels.add(c);
79            }
80        }
81
82        // Sort vowels by ASCII value (ascending).
83        Collections.sort(vowels);
84
85        // Write sorted vowels back into their original positions.
86        char[] result = s.toCharArray();
87        int vowelIndex = 0;
88        for (int pos = 0; pos < result.length; pos++) {
89            if (vowelSet.contains(result[pos])) {
90                result[pos] = vowels.get(vowelIndex++);
91            }
92        }
93
94        return new String(result);
95    }
96}
97
1class Solution {
2public:
3    string sortVowels(string s) {
4        // Set of all vowels (both lowercase and uppercase)
5        unordered_set<char> vowel_set = {'a', 'e', 'i', 'o', 'u',
6                                         'A', 'E', 'I', 'O', 'U'};
7
8        // Collect every vowel that appears in the string
9        vector<char> vowels;
10        for (char c : s) {
11            if (vowel_set.count(c)) {
12                vowels.push_back(c);
13            }
14        }
15
16        // Sort vowels in nondecreasing ASCII order
17        sort(vowels.begin(), vowels.end());
18
19        // Rebuild the answer, filling vowel positions in sorted order
20        string ans = s;
21        int idx = 0;
22        for (int k = 0; k < static_cast<int>(s.size()); k++) {
23            if (vowel_set.count(s[k])) {
24                ans[k] = vowels[idx++];
25            }
26        }
27
28        return ans;
29    }
30};
31```
32
33If you intend to keep the exact structure of your original code (using a count map), here is a faithful, standardized rewrite that preserves your logic — but with the comparator **fixed** to sort by character value, which is what the problem actually needs:
34
35```cpp
36class Solution {
37public:
38    string sortVowels(string s) {
39        // Set of vowels to check membership quickly
40        unordered_set<char> vowel_set = {'a', 'e', 'i', 'o', 'u',
41                                         'A', 'E', 'I', 'O', 'U'};
42
43        // Distinct vowels and their occurrence counts
44        vector<char> vowels;
45        unordered_map<char, int> count;
46        for (char c : s) {
47            if (!vowel_set.count(c)) {
48                continue;
49            }
50            if (!count.count(c)) {
51                vowels.push_back(c);  // record each distinct vowel once
52            }
53            count[c]++;
54        }
55
56        // Sort distinct vowels in nondecreasing ASCII order
57        sort(vowels.begin(), vowels.end(), [&](char a, char b) {
58            return a < b;
59        });
60
61        // Fill vowel positions, consuming each vowel by its count
62        string ans = s;
63        int i = 0;
64        for (int k = 0; k < static_cast<int>(s.size()); k++) {
65            if (!vowel_set.count(s[k])) {
66                continue;
67            }
68            char c = vowels[i];
69            ans[k] = c;
70            if (--count[c] == 0) {
71                i++;  // move to the next distinct vowel
72            }
73        }
74
75        return ans;
76    }
77};
78
1/**
2 * Sorts the vowels in the string in nondecreasing order of their ASCII values,
3 * while keeping all consonants in their original positions.
4 *
5 * @param s - The input string
6 * @returns The string with vowels sorted and consonants unchanged
7 */
8function sortVowels(s: string): string {
9    // Set of vowels (both lowercase and uppercase) for O(1) membership checks
10    const vowelSet: Set<string> = new Set('aeiouAEIOU');
11
12    // Collect all vowels from the string
13    const vowels: string[] = [];
14    for (const ch of s) {
15        if (vowelSet.has(ch)) {
16            vowels.push(ch);
17        }
18    }
19
20    // Sort vowels by ASCII value (nondecreasing order)
21    vowels.sort((a, b) => a.charCodeAt(0) - b.charCodeAt(0));
22
23    // Rebuild the result: place sorted vowels back, keep consonants in place
24    const result: string[] = s.split('');
25    let vowelIndex = 0;
26    for (let i = 0; i < result.length; i++) {
27        if (vowelSet.has(result[i])) {
28            result[i] = vowels[vowelIndex];
29            vowelIndex++;
30        }
31    }
32
33    return result.join('');
34}
35```
36
37### Key Changes Explained
38
391. **Fixed the core logic**: Replaced frequency-based sorting with **ASCII-value sorting**, which is what the problem actually requires. Sorting by count would not produce the correct lexicographical order.
40
412. **Included uppercase vowels**: The original `Set('aeiou')` missed uppercase vowels (`A, E, I, O, U`). The problem expects both cases to be treated as vowels, so `Set('aeiouAEIOU')` is correct.
42
433. **Simplified data structures**: Removed the unnecessary `Map` for counting. A simple array of vowels combined with an index pointer is cleaner and avoids the bug-prone counting logic.
44
454. **Standardized naming**:
46   - `st` → `vowelSet` (clarifies its purpose)
47   - `i` → `vowelIndex` (describes what it tracks)
48   - `k` → `i` (conventional loop counter)
49   - `ans` → `result` (more descriptive)
50
51### Complexity
52
53- **Time**: `O(n log n)` — dominated by sorting the collected vowels.
54- **Space**: `O(n)` — for the vowels array and the result character array.
55
56### Alternative Perspective (Counting Sort)
57
58Since there are only 10 distinct vowel characters, you can achieve `O(n)` time using counting sort:
59
60```typescript
61function sortVowels(s: string): string {
62    const vowelSet: Set<string> = new Set('aeiouAEIOU');
63    // Sorted vowels by ASCII: A,E,I,O,U (65,69,73,79,85), a,e,i,o,u (97,101,105,111,117)
64    const order: string[] = ['A', 'E', 'I', 'O', 'U', 'a', 'e', 'i', 'o', 'u'];
65    const count: Map<string, number> = new Map();
66
67    // Count occurrences of each vowel
68    for (const ch of s) {
69        if (vowelSet.has(ch)) {
70            count.set(ch, (count.get(ch) || 0) + 1);
71        }
72    }
73
74    // Build the result, emitting vowels in ASCII order
75    const result: string[] = s.split('');
76    let orderIndex = 0;
77    for (let i = 0; i < result.length; i++) {
78        if (vowelSet.has(result[i])) {
79            // Advance to the next vowel that still has remaining count
80            while ((count.get(order[orderIndex]) || 0) === 0) {
81                orderIndex++;
82            }
83            result[i] = order[orderIndex];
84            count.set(order[orderIndex], (count.get(order[orderIndex]) || 0) - 1);
85        }
86    }
87
88    return result.join('');
89}
90

Time and Space Complexity

  • Time Complexity: O(n + |Σ| log |Σ|)

    Where n is the length of the string s and Σ is the set of distinct vowels that appear in the string. The analysis is as follows:

    • The first loop iterates over every character in s to identify vowels and count their occurrences using cnt, costing O(n). The check c not in st is O(1) since st is a set, and the vowels list contains at most |Σ| distinct vowels.
    • Sorting the vowels list by frequency takes O(|Σ| log |Σ|). Since the vowel set is limited to aeiou, |Σ| ≤ 5, but it is kept in general form here.
    • The second loop iterates over s again to fill in the answer in O(n). Each character placement and counter decrement is O(1).
    • Joining the result list into a string costs O(n).

    Combining these, the total time complexity is O(n + |Σ| log |Σ|).

  • Space Complexity: O(n + |Σ|)

    Where n is the length of the string and Σ is the set of distinct vowels. The analysis is as follows:

    • The set st holds a fixed number of vowels, costing O(1).
    • The vowels list and the cnt Counter each store at most |Σ| distinct vowels, costing O(|Σ|).
    • The ans list stores all n characters of the string, costing O(n). The final joined string also takes O(n).

    Combining these, the total space complexity is O(n + |Σ|).

Common Pitfalls

Pitfall 1: Mismatched Sorting Criteria Between the Problem and the Code

The single most dangerous trap here is a conflict between what the problem statement asks for and what the code actually does. Read carefully:

  • The problem description demands sorting vowels by non-increasing frequency, with ties broken by first occurrence.
  • The provided code sorts vowels by ASCII value (using a plain sort() or sorted()).

These are two completely different algorithms that happen to share scaffolding. If you trust the code blindly, you will produce wrong answers for the stated problem.

Example: For s = "leetcode", the vowels are e, e, o, e → frequencies e:3, o:1.

  • Frequency-based (problem's requirement): e (freq 3) comes before o (freq 1) → vowels placed as e, e, e, o → result "leetcede" ... wait, positions matter: indices 1,2,5,7 get e,e,e,o → "leetcedo".
  • ASCII-based (code's behavior): sorted vowels are e,e,e,o (since 'e' < 'o') → coincidentally the same here, but only by accident.

Try s = "aeiou" where all frequencies are equal:

  • Frequency-based with first-occurrence tiebreak: order stays a,e,i,o,u.
  • ASCII-based: a,e,i,o,u — same again because input was already sorted.

Now s = "uoiea" (each frequency 1):

  • Frequency-based first-occurrence: u,o,i,e,a (original order preserved).
  • ASCII-based: a,e,i,o,u — different!

Solution: Decide which specification is authoritative before coding, then make the sort key match it exactly.

# If the PROBLEM (non-increasing frequency, first-occurrence tiebreak) is correct:
class Solution:
    def sortVowels(self, s: str) -> str:
        vowel_set = set("aeiouAEIOU")
        counter = Counter()
        distinct_vowels = []
        for char in s:
            if char not in vowel_set:
                continue
            if char not in counter:
                distinct_vowels.append(char)  # preserves first-occurrence order
            counter[char] += 1

        # Negative count => non-increasing; stable sort keeps first-occurrence tie order
        distinct_vowels.sort(key=lambda c: -counter[c])

        result = list(s)
        index = 0
        for pos, char in enumerate(s):
            if char not in vowel_set:
                continue
            current = distinct_vowels[index]
            result[pos] = current
            counter[current] -= 1
            if counter[current] == 0:
                index += 1
        return "".join(result)

Pitfall 2: Forgetting the Stability Requirement for the Tiebreaker

If you do sort by frequency, the first-occurrence tiebreaker silently relies on two things:

  1. distinct_vowels being built in first-occurrence order (only appended on first sighting).
  2. Python's sort being stable, so equal-frequency vowels retain that order.

If you instead build distinct_vowels from a set or counter.keys() (in older interpreters or other languages), insertion order is lost and the tiebreak breaks even though the frequency sort looks correct.

Solution: Always populate the candidate list in the required tiebreak order, and never reconstruct it from an unordered container.

Pitfall 3: Mutating a String Directly

Python strings are immutable, so s[pos] = current raises TypeError. The code correctly converts to a list first (result = list(s)), but a common slip is to forget this conversion or to forget "".join(result) at the end.

Solution: Convert to a list for in-place edits, then "".join(...) to return a string.

Pitfall 4: Advancing the Pointer Incorrectly in the Counter Version

In the counter-based rebuild, the pointer index advances only when a vowel's count hits zero. Two subtle bugs:

  • Decrementing the wrong key (decrement current, not char, since char is the original character at that position which may differ from the one being placed).
  • Advancing index unconditionally each iteration (which would skip vowels still having remaining copies).

Solution: Decrement the placed vowel and gate the pointer advance on counter[current] == 0. Note the simpler "collect-all-and-sort" alternative sidesteps this entirely by advancing the pointer once per vowel position — preferring that version eliminates this whole class of bug.

Pitfall 5: Uppercase Handling Inconsistency

The problem says lowercase English characters, yet the code defends against "aeiouAEIOU". This is harmless for the stated constraints, but with ASCII sorting it changes results dramatically because uppercase letters sort before lowercase. If the real task were case-sensitive frequency sorting, the expanded set combined with ASCII order could produce surprising placements.

Solution: Match the vowel set to the actual input domain. For strictly lowercase input, set("aeiou") is sufficient and avoids accidental case-related ordering surprises.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which data structure is used in a depth first search?

Recommended Readings

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Explained

Recursion If you prefer videos here's a video that explains recursion in a fun and easy way Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask him

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity describes how the time needed

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More