3913. Sort Vowels by Frequency

📘 題目敘述

給定一個只包含小寫英文字母的字串 s。

請只重新排列字串中的母音，讓它們依照出現頻率遞減的順序排列。

如果多個母音的出現頻率一樣，則依照它們在原字串中第一次出現的位置來決定順序。

最後回傳修改後的字串。

母音只有：

• 'a'
• 'e'
• 'i'
• 'o'
• 'u'

條件限制

• 1 <= s.length <= 10^5
• s 只包含小寫英文字母

🧠 解題思路

我這題的想法是先把所有母音的位置記下來，再統計五種母音各出現幾次，最後按照題目規則決定母音應該怎麼排，再依序填回原本那些母音位置。

因為題目只允許重排母音，子音完全不能動，所以整體流程就是：

• 先找出哪些位置是母音
• 再統計每種母音的頻率
• 同時記錄每種母音第一次出現的位置
• 接著按照「頻率大到小，如果頻率相同就看第一次出現位置」的規則，把母音依序放回那些母音位置

我這份寫法因為母音種類固定只有 5 種，所以直接每次在這 5 種母音裡找目前應該先放哪一種就可以了。

所有變數

• pos：記錄原字串中所有母音出現的位置，後面要把排好順序的母音填回這些位置
• p：目前填到 pos 的第幾個位置
• n：字串長度
• a：五種母音各自的出現次數
• fst：五種母音第一次出現在字串中的位置，如果沒出現就保持 -1
• v：固定存五種母音 'a'、'e'、'i'、'o'、'u'
• m：目前這一輪要選來填回去的母音種類編號

🪜 主要流程步驟

略，同題解內容完全照比賽筆記撰寫。

⏱️ 複雜度

設 n = s.length。

• 時間複雜度：O(n)
• 空間複雜度：O(n)

💻 程式碼實作

class Solution {
public:
    string sortVowels(string s) {
        vector<int> pos;
        int p = 0;
        int n = s.size();
        int a[5] = {0};
        int fst[5] = {-1, -1, -1, -1, -1};
        char v[5] = {'a', 'e', 'i', 'o', 'u'};
        for (int k = 0; k < n; k++) {
            for (int j = 0; j < 5; j++) {
                if (s[k] == v[j]) {
                    a[j]++;
                    pos.push_back(k);
                    if (fst[j] == -1) {
                        fst[j] = k;
                    }
                    break;
                }
            }
        }
        for (int i = 0; i < 5; i++) {
            int m = 0;
            for (int j = 1; j < 5; j++) {
                if (a[j] > a[m]) {
                    m = j;
                } else if (a[j] == a[m]) {
                    if (fst[j] < fst[m] && fst[j] != -1) {
                        m = j;
                    }
                }
            }
            while (a[m] > 0) {
                s[pos[p]] = v[m];
                p++;
                a[m]--;
            }
        }
        return s;
    }
};

🔗 題目連結

https://leetcode.com/problems/sort-vowels-by-frequency/