題目資訊

• 題目編號: 1358
• 題目連結: Number of Substrings Containing All Three Characters
• 主題: Hash Table, String, Sliding Window

題目敘述

給定一個只包含字元 a、b 和 c 的字串 s。

返回包含這些字元 a、b 和 c 中至少出現一次的子字串的數量。

範例 1:

輸入: s = "abcabc"
輸出: 10
解釋: 包含至少一次所有字元 *a*、*b* 和 *c* 的子字串為 "abc"、"abca"、"abcab"、"abcabc"、"bca"、"bcab"、"bcabc"、"cab"、"cabc" 和 "abc" (重複計算)。

範例 2:

輸入: s = "aaacb"
輸出: 3
解釋: 包含至少一次所有字元 *a*、*b* 和 *c* 的子字串為 "aaacb"、"aacb" 和 "acb"。

範例 3:

輸入: s = "abc"
輸出: 1

約束條件:

• $3 \leq s.\text{長度} \leq 5 \times 10^4$
• $s$ 僅由字元 a、b 或 c 組成。

直覺

此問題要求我們計算字串 s 中至少包含一個 ‘a’、‘b’ 和 ‘c’ 的子字串的數量。問題的複雜性在於需要確認每個子字串是否包含所有這三個字符，這需要仔細追蹤它們的出現位置。一個有效的方法是使用滑動窗口技術，並在我們遍歷字串過程中追蹤 ‘a’、‘b’ 和 ‘c’ 的最近出現位置。

解法

此解法使用單次遍歷字串 s，重點是維護對應 ‘a’、‘b’ 和 ‘c’ 字符的最新索引位置。以下是該方法的詳細細節：

1. 初始化：首先，我們初始化一個結果變量 result 為零，用來最終儲存符合條件的子字串數量。此外，我們維護一個向量 last_seen_index 並初始化為 {-1, -1, -1}。此向量用來記錄 ‘a’、‘b’ 和 ‘c’ 分別在字符串中最近一次出現的索引位置。

2. 遍歷：當我們遍歷字串 s 中的每個字符時，執行以下操作：

   • 更新當前字符對應的 last_seen_index。透過將字符轉換為索引來完成，即使用 s[i] - 'a'，對於 ‘a’ 計算得 0，‘b’ 計算得 1，‘c’ 計算得 2，並將當前索引 i 分別賦值給 last_seen_index 向量中的相應位置。

3. 確認有效子字串：對於每個索引 i：

   • 計算 last_seen_index 中的最小值，利用 min_element 來代表 ‘a’、‘b’ 和 ‘c’ 最後記錄位置中最早的索引。
   • 如果此最小值不是 -1，即表示所有字符（‘a’、‘b’、‘c’）最少都在當前索引之前出現過一次。那麼，以 i 為結尾的有效子字串數量將是 min_index + 1。這是因為從索引 0 到 min_index 任意開始的子字串，並以 i 結尾的將包含至少一個 ‘a’、‘b’ 和 ‘c’。

4. 更新結果：將上一步計算的數量加到 result。

5. 返回結果：完成循環後，result 變量保存了滿足條件的子字串總數，並作為最終輸出返回。

此方法確保我們可以在單次遍歷字串中有效地找到所有有效子字串，其時間複雜度為 $O(n)$，其中 $n$ 是字串 s 的長度。

程式碼

C++

class Solution {
public:
    int numberOfSubstrings(string s) {
        int result = 0;  // 用於儲存有效子字串的數量的變數
        vector<int> last_seen_index = {-1, -1, -1};  // 用於追蹤字元 'a'、'b' 和 'c' 最後出現位置的陣列
        
        for (int i = 0; i < s.size(); i++) {
            // 更新當前字元的最後出現位置
            last_seen_index[s[i] - 'a'] = i; 
            
            // 找出 'a'、'b' 和 'c' 最後出現位置中的最小值
            int min_index = *min_element(last_seen_index.begin(), last_seen_index.end());
            
            // 如果字元 'a'、'b' 和 'c' 均至少出現過一次，則更新結果
            if (min_index != -1) {
                result += min_index + 1;
            }
        }
        
        return result;  // 返回有效子字串的總數量
    }
};

Python

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        result = 0  # 用於存儲有效子字串的數量
        last_seen_index = [-1, -1, -1]  # 用於記錄字元 'a', 'b', 和 'c' 最後出現的索引
        
        for i in range(len(s)):
            # 更新當前字元最後出現的索引
            last_seen_index[ord(s[i]) - ord('a')] = i 
            
            # 找出字元 'a', 'b', 和 'c' 最後一次出現索引中的最小值
            min_index = min(last_seen_index)
            
            # 如果字元 'a', 'b', 和 'c' 都至少出現過一次，更新結果
            if min_index != -1:
                result += min_index + 1
        
        return result  # 返回有效子字串的總數量

複雜度分析

• 時間複雜度: $O(n)$
  時間複雜度為 $O(n)$，因為我們在 for 迴圈中恰好遍歷一次字串 s。對於字串中的每個字符，我們更新 last_seen_index 陣列並使用 min_element 函數計算 min_index，這兩者都是常數時間操作 $O(1)$。因此，整體時間複雜度相對於字串的長度是線性的。
• 空間複雜度: $O(1)$
  空間複雜度為 $O(1)$，因為我們使用了固定量的額外存儲。last_seen_index 陣列的大小為常數 3，與輸入大小無關，並且其他變數使用了常數空間。因此，空間複雜度是常數。