3913. Sort Vowels by Frequency

Description

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 <= 10⁵
s consists of lowercase English letters

Solutions

Solution 1: Counting + Custom Sorting

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

We then sort the \(\textit{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 \(\textit{vowels}\) list, and update the frequency in the hash table. When the frequency of a vowel becomes 0, we move the pointer in the \(\textit{vowels}\) list forward by one.

Python3JavaC++GoTypeScript

class Solution:
    def sortVowels(self, s: str) -> str:
        st = set("aeiou")
        vowels = []
        cnt = Counter()
        for c in s:
            if c not in st:
                continue
            if c not in cnt:
                vowels.append(c)
            cnt[c] += 1
        vowels.sort(key=lambda c: -cnt[c])
        ans = list(s)
        i = 0
        for k, c in enumerate(s):
            if c not in st:
                continue
            ans[k] = c = vowels[i]
            cnt[c] -= 1
            if cnt[c] == 0:
                i += 1
        return "".join(ans)

class Solution {
    public String sortVowels(String s) {
        Set<Character> st = Set.of('a', 'e', 'i', 'o', 'u');
        List<Character> vowels = new ArrayList<>();
        Map<Character, Integer> cnt = new HashMap<>();
        for (char c : s.toCharArray()) {
            if (!st.contains(c)) {
                continue;
            }
            if (!cnt.containsKey(c)) {
                vowels.add(c);
            }
            cnt.merge(c, 1, Integer::sum);
        }
        vowels.sort((a, b) -> cnt.get(b) - cnt.get(a));
        char[] ans = s.toCharArray();
        int i = 0;
        for (int k = 0; k < s.length(); k++) {
            char c = s.charAt(k);
            if (!st.contains(c)) {
                continue;
            }
            ans[k] = c = vowels.get(i);
            cnt.merge(c, -1, Integer::sum);
            if (cnt.get(c) == 0) {
                i++;
            }
        }
        return new String(ans);
    }
}

class Solution {
public:
    string sortVowels(string s) {
        unordered_set<char> st = {'a', 'e', 'i', 'o', 'u'};
        vector<char> vowels;
        unordered_map<char, int> cnt;
        for (char c : s) {
            if (!st.count(c)) {
                continue;
            }
            if (!cnt.count(c)) {
                vowels.push_back(c);
            }
            cnt[c]++;
        }
        sort(vowels.begin(), vowels.end(), [&](char a, char b) {
            return cnt[a] > cnt[b];
        });
        string ans = s;
        int i = 0;
        for (int k = 0; k < s.size(); k++) {
            if (!st.count(s[k])) {
                continue;
            }
            char c = vowels[i];
            ans[k] = c;
            if (--cnt[c] == 0) {
                i++;
            }
        }
        return ans;
    }
};

func sortVowels(s string) string {
    st := map[rune]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true}
    var vowels []rune
    cnt := make(map[rune]int)
    for _, c := range s {
        if !st[c] {
            continue
        }
        if _, ok := cnt[c]; !ok {
            vowels = append(vowels, c)
        }
        cnt[c]++
    }
    sort.Slice(vowels, func(i, j int) bool {
        return cnt[vowels[i]] > cnt[vowels[j]]
    })
    ans := []rune(s)
    i := 0
    for k, c := range s {
        if !st[c] {
            continue
        }
        char := vowels[i]
        ans[k] = char
        cnt[char]--
        if cnt[char] == 0 {
            i++
        }
    }
    return string(ans)
}

function sortVowels(s: string): string {
    const st = new Set('aeiou');
    const vowels: string[] = [];
    const cnt: Map<string, number> = new Map();
    for (const c of s) {
        if (!st.has(c)) {
            continue;
        }
        if (!cnt.has(c)) {
            vowels.push(c);
        }
        cnt.set(c, (cnt.get(c) || 0) + 1);
    }
    vowels.sort((a, b) => (cnt.get(b) || 0) - (cnt.get(a) || 0));
    const ans = s.split('');
    let i = 0;
    for (let k = 0; k < s.length; k++) {
        let c = s[k];
        if (!st.has(c)) {
            continue;
        }
        c = vowels[i];
        ans[k] = c;
        cnt.set(c, (cnt.get(c) || 0) - 1);
        if (cnt.get(c) === 0) {
            i++;
        }
    }
    return ans.join('');
}

3913. Sort Vowels by Frequency

Description

Solutions

Solution 1: Counting + Custom Sorting

Comments