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

題意

給定一個字串 s，找出長度為 k 的 substring 內含有最多母音 (a、e、i、o、u) 的數量

限制

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.
• 1 <= k <= s.length

思考

維護一個長度為 k 的 window，並在移動過程中紀錄 window 內的母音數。

另外，這樣的作法只需要走訪字串一次，因此時間複雜度為 O(n)。由於在運算過程中只需要少數幾個變數來儲存狀態，沒有額外使用其他結構，故空間複雜度為 O(1)。

Solution

#define isVowel(ch) (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')

class Solution {
public:
    int maxVowels(string s, int k) {
        const int n = s.size();
        int count = 0;
        for (int i = 0; i < k; i += 1) {
            if (isVowel(s[i])) {
                count += 1;
            }
        }

        int ans = count;
        for (int i = 0; i < n - k; i += 1) {
            if (isVowel(s[i])) {
                count -= 1;
            }
            if (isVowel(s[i + k])) {
                count += 1;
            }
            ans = max(ans, count);
        }
        return ans;
    }
};