1456. Maximum Number of Vowels in a Substring of Given Length

📘 題目敘述

給定一個字串 s 與一個整數 k，請找出長度恰好為 k 的連續子字串中，母音（vowels）數量最多的那一個，並回傳該最大母音數量。

母音定義為：'a'、'e'、'i'、'o'、'u'。

條件限制

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

🧠 解題思路

這題和 Maximum Average Subarray I 非常像，本質都是：

在固定長度 k 的連續區間中，找一個數值最大的區間。

只是這題不是算總和，而是算區間內母音的個數。

因此我同樣使用 Sliding Window（滑動視窗） 的方式：

• 先計算第一個長度為 k 的子字串中有幾個母音
• 每次視窗往右移一格，就更新新進來與移出去的字元

所有變數

• vol：目前為止找到的最大母音數量
• nvol：目前滑動視窗內的母音數量
• k：子字串固定長度
• v：長度為 5 的陣列，存所有母音字元 {a, e, i, o, u}

🪜 主要流程步驟

第一步：計算第一個長度為 k 的子字串母音數量

• 掃描 s[0] ~ s[k-1]
• 每個字元都和母音陣列 v 比對
• 若是母音，就把 vol++
• 初始化完成後：vol 為第一個視窗的母音數，nvol = vol

第二步：滑動視窗並即時更新母音數量

從索引 l = k 開始一路往右滑：

• 新進來的字元 s[l] 若是母音 → nvol++
• 被移出去的字元 s[l - k] 若是母音 → nvol--

這樣就完成一次視窗移動的更新。

第三步：更新最大母音數

• 每次更新完 nvol 後，比較 nvol 與目前最大值 vol
• 若 nvol > vol，就更新 vol

第四步：回傳結果

• 所有視窗都檢查完後，vol 就是長度為 k 的子字串中最多的母音數量

💻 程式碼實作

class Solution {
public:
    int maxVowels(string s, int k) {
        int vol = 0;
        int nvol = 0;
        char v[5] = {'a', 'e', 'i', 'o', 'u'};
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < 5; j++) {
                if (s[i] == v[j]) {
                    vol++;
                    break;
                }
            }
        }
        nvol = vol;
        for (int l = k; l < s.size(); l++) {
            for (int j = 0; j < 5; j++) {
                if (s[l] == v[j]) {
                    nvol++;
                    break;
                }
            }
            for (int j = 0; j < 5; j++) {
                if (s[l - k] == v[j]) {
                    nvol--;
                    break;
                }
            }
            if (nvol > vol) {
                vol = nvol;
            }
        }
        return vol;
    }
};

🔗 題目連結

https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/