LeetCode 3913 - Sort Vowels by Frequency

Difficulty: 🟡 Medium
Topics: String, Sorting, Counting

Solution

Problem Understanding

The problem requires us to reorder the vowels in a given string s based on their frequency, while keeping all consonants in their original positions. Specifically, the vowels must appear in non-increasing order of frequency. If two vowels have the same frequency, the one that appeared first in the string should come first in the sorted order.

The input is a string consisting only of lowercase English letters. The output is another string of the same length where vowels have been rearranged as described, and consonants remain untouched.

Constraints tell us that the string can be as long as 100,000 characters, so a solution with worse than linearithmic time complexity might be inefficient. Edge cases to consider include strings with all vowels, strings with no vowels, strings where all vowels occur once, or strings where some vowels have the same frequency.

Important points to note:

Only vowels are rearranged.
Frequencies dictate ordering first, then first occurrence.
Consonants must remain in the same positions.
Input size can be large, so efficiency matters.

Approaches

Brute Force

A naive approach would be to count frequencies of all vowels, then repeatedly scan the string to find the next vowel to place according to frequency and first occurrence order. One could use a priority queue or repeatedly sort the remaining vowels before placing each one. While this is correct, sorting repeatedly or scanning repeatedly results in high time complexity, potentially O(n²) in the worst case.

Optimal Approach

The key observation is that we can separate the problem into three parts: identify vowels and their positions, compute frequency and first occurrence, and then sort vowels once based on these two criteria. We then place the sorted vowels back into the original positions. This avoids repeated scanning or sorting. Counting and sorting operations are linear and logarithmic, respectively, leading to an efficient solution suitable for large inputs.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeated scanning and placement of vowels
Optimal	O(n log k)	O(n)	Count frequencies, sort vowels by frequency and first occurrence, place them back

Here n is the length of the string and k is the number of unique vowels (at most 5).

Algorithm Walkthrough

Identify vowels and their positions: Iterate through the string, collecting all vowels along with their indices in a list. This allows us to place them back in the correct locations later. Also, record the first occurrence index for each vowel and increment a frequency counter for each vowel.
Sort vowels: Using the frequency map and first occurrence map, sort the vowels by decreasing frequency. If frequencies are equal, use the first occurrence as a tiebreaker. Since the number of unique vowels is small (≤5), this sorting is essentially constant time.
Place vowels back: Iterate through the original string again, and for each vowel position, replace it with the next vowel from the sorted list. Consonants remain unchanged.
Return the modified string: Convert the character array back to a string and return it.

Why it works: This method works because it preserves the positions of consonants, ensures the ordering of vowels according to frequency and first occurrence, and guarantees each vowel is used exactly once. The sorting is stable with respect to frequency and first occurrence.

Python Solution

class Solution:
    def sortVowels(self, s: str) -> str:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        freq = {}
        first_occurrence = {}
        vowel_list = []

        for i, ch in enumerate(s):
            if ch in vowels:
                vowel_list.append(ch)
                freq[ch] = freq.get(ch, 0) + 1
                if ch not in first_occurrence:
                    first_occurrence[ch] = i

        # Sort vowels by frequency descending, then first occurrence
        sorted_vowels = sorted(vowel_list, key=lambda x: (-freq[x], first_occurrence[x]))

        result = []
        v_idx = 0
        for ch in s:
            if ch in vowels:
                result.append(sorted_vowels[v_idx])
                v_idx += 1
            else:
                result.append(ch)

        return ''.join(result)

Implementation Explanation

The code first builds a set of vowels and iterates through the string to count frequencies and record first occurrences. It also builds a list of vowels to be sorted. The sorted function uses a key that sorts primarily by negative frequency (to get descending order) and secondarily by the first occurrence. Finally, we rebuild the string by replacing each vowel with its sorted counterpart while leaving consonants unchanged.

Go Solution

import "sort"

func sortVowels(s string) string {
    vowels := map[rune]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true}
    freq := map[rune]int{}
    firstOccurrence := map[rune]int{}
    vowelList := []rune{}

    for i, ch := range s {
        if vowels[ch] {
            vowelList = append(vowelList, ch)
            freq[ch]++
            if _, ok := firstOccurrence[ch]; !ok {
                firstOccurrence[ch] = i
            }
        }
    }

    sort.SliceStable(vowelList, func(i, j int) bool {
        if freq[vowelList[i]] != freq[vowelList[j]] {
            return freq[vowelList[i]] > freq[vowelList[j]]
        }
        return firstOccurrence[vowelList[i]] < firstOccurrence[vowelList[j]]
    })

    result := []rune{}
    vIdx := 0
    for _, ch := range s {
        if vowels[ch] {
            result = append(result, vowelList[vIdx])
            vIdx++
        } else {
            result = append(result, ch)
        }
    }

    return string(result)
}

Go-specific Notes: Go uses rune to handle Unicode characters safely. The sort.SliceStable function is used to ensure stable sorting based on frequency and first occurrence. Maps are used for frequency and first occurrence similarly to Python dictionaries.

Worked Examples

Example 1: s = "leetcode"

Step	vowel_list	freq	first_occurrence	sorted_vowels	result
initial	['e', 'e', 'o', 'e']	{'e':3, 'o':1}	{'e':1, 'o':4}	['e','e','e','o']	"leetcedo"

Example 2: s = "aeiaaioooa"

Step	vowel_list	freq	first_occurrence	sorted_vowels	result
initial	['a','e','i','a','a','i','o','o','o','a']	{'a':4,'e':1,'i':2,'o':3}	{'a':0,'e':1,'i':2,'o':6}	['a','a','a','a','o','o','o','i','i','e']	"aaaaoooiie"

Example 3: s = "baeiou"

Step	vowel_list	freq	first_occurrence	sorted_vowels	result
initial	['a','e','i','o','u']	{'a':1,'e':1,'i':1,'o':1,'u':1}	{'a':1,'e':2,'i':3,'o':4,'u':5}	['a','e','i','o','u']	"baeiou"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log k)	Counting vowels is O(n), sorting the vowels is O(k log k) where k≤5, placing vowels back is O(n)
Space	O(n)	We store a list of vowels of length ≤n and maps of size ≤5

Even though we write O(n log k), since k is ≤5, this is effectively O(n).

Test Cases

# Provided examples
assert Solution().sortVowels("leetcode") == "leetcedo"  # multiple vowels with different frequency
assert Solution().sortVowels("aeiaaioooa") == "aaaaoooiie"  # complex frequency sorting
assert Solution().sortVowels("baeiou") == "baeiou"  # all vowels appear once

# Edge cases
assert Solution().sortVowels("bcdfg") == "bcdfg"  # no vowels
assert Solution().sortVowels("aaaaa") == "aaaaa"  # all same vowels
assert Solution().sortVowels("aebcdaeei") == "aaeeebdei"  # mix of frequencies and positions
assert Solution().sortVowels("uioeaa") == "aaueio"  # tie-break with first occurrence
assert Solution().sortVowels("e") == "e"  # single character vowel
assert Solution().sortVowels("b") == "b"  # single character consonant

Test	Why
"leetcode"	Tests basic frequency ordering
"aeiaaioooa"	Tests