題目資訊

題目編號: 3306
題目連結: Count of Substrings Containing Every Vowel and K Consonants II
主題: Hash Table, String, Sliding Window

題目敘述

你有一個字串 word 和一個非負整數 k。

返回 word 的所有子字串中，同時包含每個元音字母（'a'、'e'、'i'、'o' 和 'u'）至少一次且正好有 k 個子音的總數。

範例 1:

輸入: word = "aeioqq", k = 1

輸出: 0

解釋:

沒有包含每個元音的子字串。

範例 2:

輸入: word = "aeiou", k = 0

輸出: 1

解釋:

唯一的子字串包含每個元音且沒有子音的是 word[0..4]，也就是 "aeiou"。

範例 3:

輸入: word = "ieaouqqieaouqq", k = 1

輸出: 3

解釋:

包含每個元音且有一個子音的子字串是：

word[0..5]，也就是 "ieaouq"。
word[6..11]，也就是 "qieaou"。
word[7..12]，也就是 "ieaouq"。

限制條件:

$5 \leq \text{word.length} \leq 2 \times 10^5$
word 僅由小寫英文字母組成。
$0 \leq k \leq \text{word.length} - 5$

直覺

此問題要求識別包含所有五個元音字母（‘a’, ’e’, ‘i’, ‘o’, ‘u’）至少一次且正好有 $k$ 個子音的子字串。在這裡，複雜性在於如何在給定約束的情況下有效地找到這樣的子字串，特別是對於字的長度。滑動窗口技術在此變得至關重要，因為它允許動態調整窗口的大小和位置，以評估不同的候選子字串，而不需要反復重新評估整個字串。

解法

此解法採用了滑動窗口方法來維持在給定字串內的動態子字串。整個過程包含若干步驟，對字串中的每個字元重複執行：

字符映射: 使用輔助函數將每個字符映射到一個索引，元音映射為索引 0 至 4，而子音則映射為索引 5。
動態窗口調整: 當窗口的右端隨著每次迭代而擴展時，它將更新一個 count 陣列，該陣列跟踪當前窗口中每個元音數量和子音的總數。
子音數量限制: 如果窗口中包含的子音多於指定的 $k$，則增大窗口的左部分直到多餘的子音被移除，以保證數量正好為 $k$。
避免元音重複: 為了避免計算包含重複元音的子字串，在所有元音都出現之前，窗口向右移動以移除多餘的元音。
驗證與累積: 在每一步，檢查當前窗口（子字串）是否包含所有的元音至少一次並且正好有 $k$ 個子音，通過使用 min_element 來確保每個元音的數量大於零並驗證子音數量是否與 $k$ 一致。如果發現有效子字串，則累積這樣的子字串的數量。

這個演算法通過針對性地調整窗口邊界來有效地評估子字串，確保條件檢查和窗口更新以最大化計算效率，符合問題的限制。

程式碼

C++

class Solution {
public:
    // 函數將元音和子音映射到特定的索引。
    // 元音映射為 0-4，而任何子音映射為 5。
    int mapCharacterToIndex(char c) {
        switch(c) {
            case 'a': return 0;
            case 'e': return 1;
            case 'i': return 2;
            case 'o': return 3;
            case 'u': return 4;
            default:  return 5;
        }
    }
    
    long long countOfSubstrings(string word, int k) {
        // 計數陣列，用於記錄元音和子音的數量。
        vector<int> count(6, 0); 
        int left = 0, right = 0;
        long long answer = 0;

        for (int i = 0; i < word.size(); i++) {
            int index = mapCharacterToIndex(word[i]);
            count[index]++;

            // 如果子音超過 'k' 個，調整窗口。
            if (index == 5 && count[index] > k) {
                while (count[index] > k) {
                    count[mapCharacterToIndex(word[right++])]--;
                }
                left = right;
            }
            
            // 確保沒有重複的元音。
            while (mapCharacterToIndex(word[right]) != 5 && count[mapCharacterToIndex(word[right])] > 1) {
                count[mapCharacterToIndex(word[right++])]--;
            }

            // 檢查目前的子字串是否包含所有元音且正好有 k 個子音。
            if (*min_element(count.begin(), count.end() - 1) > 0 && count[5] == k) {
                answer += right - left + 1;
            }
        }
        return answer;
    }
};

Python

class Solution:
    # 函數將母音和子音映射到特定索引。
    # 母音對應到 0-4，任何子音對應到 5。
    def mapCharacterToIndex(self, c):
        if c == 'a':
            return 0
        elif c == 'e':
            return 1
        elif c == 'i':
            return 2
        elif c == 'o':
            return 3
        elif c == 'u':
            return 4
        else:
            return 5
    
    def countOfSubstrings(self, word, k):
        # 計數數組，用於追蹤母音和子音的數量。
        count = [0] * 6
        left = 0
        right = 0
        answer = 0

        for i in range(len(word)):
            index = self.mapCharacterToIndex(word[i])
            count[index] += 1

            # 如果有超過 'k' 個子音，調整窗口。
            if index == 5 and count[index] > k:
                while count[index] > k:
                    count[self.mapCharacterToIndex(word[right])] -= 1
                    right += 1
                left = right
            
            # 確保母音不重複。
            while self.mapCharacterToIndex(word[right]) != 5 and count[self.mapCharacterToIndex(word[right])] > 1:
                count[self.mapCharacterToIndex(word[right])] -= 1
                right += 1

            # 檢查當前子字串是否包含所有母音且恰好有 k 個子音。
            if min(count[:5]) > 0 and count[5] == k:
                answer += right - left + 1

        return answer

複雜度分析

時間複雜度: $O(n)$
該算法通過單個循環遍歷輸入字串 word 一次，使得時間複雜度為 $O(n)$，其中 $n$ 為字串的長度。在循環中，該算法執行常數時間操作，包括對計數數組的更新和條件檢查。內部的 while 循環移動 right 指針以調整窗口，但總體上，它們在算法過程中不超過 $O(n)$ 操作，因為每個字符最多被處理兩次（一次向前移動 right，一次可能是為了維持窗口條件而向後移動 right）。
空間複雜度: $O(1)$
該算法的空間複雜度為 $O(1)$，表示常數空間使用。這是因為該算法使用了固定大小的包含六個整數的數組來跟蹤元音和輔音的計數，並且不使用任何隨輸入字串 word 大小而變化的數據結構。所使用的變數和數據結構的大小與輸入大小無關，因此得出常數空間複雜度。

CS Note
En

Leetcode 3306. Count of Substrings Containing Every Vowel and K Consonants II

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析