[LeetCode 解題紀錄] 1456. Maximum Number of Vowels in a Substring of Given Length

https://leetcode.com/

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

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

Problem:

Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.

Example 1:

Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.

Example 2:

Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.

Example 3:

Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.

Constraints:

• 1 <= s.length <= 105
• s consists of lowercase English letters.
• 1 <= k <= s.length

題意

一個給定的字符 s 和一個整數 k，要求找出 s 中長度為 k 的子字串中，包含最多母音字母的數量。英文中的母音字母包括 ‘a’, ‘e’, ‘i’, ‘o’, ‘u’。

問題解析：

• 找出 k 子字串中最多的母音數量
• 子字串 → 是連續的字串
• 子字串長度固定 → Sliding Windows
• 需要一個 mapping table 來記錄母音 → 可以使用 Array 或是 Set

解法

暴力解

雖然這題其實蠻明顯可以看出來，使用 Sliding Windows 會是最佳解，但如果一開始沒有辦法直接想到，不妨先從最直覺的方法來思考，再一步一步的把你的答案變得更好。

檢查所有可能的長度為 k 的子字串，計算每個子字串中的母音數量，並記錄最大值，這種方法的時間複雜度是 O(n*k)，這個解法在字串長度較小時是沒有什麼問題的。

const maxVowels = function(s, k) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
    let maxVowels = 0;

    for (let i = 0; i <= s.length - k; i++) {
        let currVowels = 0;
        for (let j = 0; j < k; j++) {
            if (vowels.has(s[i + j])) {
                currVowels++;
            }
        }
        maxVowels = Math.max(maxVowels, currVowels);
    }

    return maxVowels;
};

• 時間複雜度：O(n * k) → 因為最差情況需要檢查所有 n * k 次
• 空間複雜度：O(1) → 紀錄母音固定數量的變量，與輸入字符串的大小無關

使用 Sliding Window

Sliding Window 的基礎概念，就是透過不斷移動視窗的位置，來更新當下最佳的值，或是紀錄最終的答案。

Sliding Window 概念複習：

演算法筆記系列 — Two Pointer 與Sliding Window

1. 計算初始視窗的母音數量：

• 遍歷字串的前 k 個字母，計算初始視窗中的母音數量並存儲在 currentCount 中。

2. 滑動視窗遍歷字串：

• 從第 k 個字母開始，逐個字母移動視窗。
• 每次移動時，檢查移出視窗的字母是否是母音，如果是，則 currentCount 減一。
• 檢查移入視窗的字母是否是母音，如果是，則 currentCount 加一。
• 更新 maxCount，將其設置為 maxCount 和 currentCount 中的較大值。

const maxVowels = function(s, k) {
    // 使用 Set 來存母音字母，檢查是否為母音的時間複雜度為 O(1)
    const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
    let maxVowels = 0;
    let currVowels = 0;

    // 初始化視窗的母音數量
    for (let i = 0; i < k; i++) {
        if (vowels.has(s[i])) {
            currVowels++;
        }
    }
    maxVowels = currVowels;

    // 滑動窗口遍歷字串
    for (let i = k; i < s.length; i++) {
        // 移出視窗的字母
        if (vowels.has(s[i - k])) {
            currVowels--;
        }
        // 移入視窗的字母
        if (vowels.has(s[i])) {
            currVowels++;
        }
        // 更新最大母音數量
        maxVowels = Math.max(maxVowels, currVowels);
    }

    return maxVowels;
};

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

更多演算法與資料結構文章：

基礎演算法與資料結構學習筆記