LeetCode 解題筆記：1358. Number of Substrings Containing All Three Characters

作者：王一哲
日期：2026年6月30日


LeetCode 題目連結：1358. Number of Substrings Containing All Three Characters

解題想法

中等難度題。題目給定只有 $a, b, c$ 的字串 $s$，要找出同時有 $a, b, c$ 至少各 $1$ 個字母的子字串數量，由於字串長度最長為 $5 \times 10^4$，如果用兩層 for 迴圈跑過所有的子字串組合，時間複雜度為 $O(n^2)$，一定會超時。改用字典 $pos$ 儲存字母 $a, b, c$ 最後一次出現的索引值，預設值為 $-1$，代表這個字母還沒有出現過。用一層 for 迴圈掃過字串 $s$，先更新 $s[i]$ 對應的索引值，找出 $a, b, c$ 字母對應的索引值之中的最小值為 min_idx，如果 min_idx != -1，代表 $a, b, c$ 都有出現在子字串內，答案 $ans$ 要加上 min_idx + 1。以範例測資1 s = "abcabc" 為例：

1. $i = 2$，$pos['a'] = 0, pos['b'] = 1, pos['c'] = 2$，min_idx = 0，有 1 組符合要求的子字串 abc。
2. $i = 3$，$pos['a'] = 3, pos['b'] = 1, pos['c'] = 2$，min_idx = 1，有 2 組符合要求的子字串 abca, bca。
3. $i = 4$，$pos['a'] = 3, pos['b'] = 4, pos['c'] = 2$，min_idx = 2，有 3 組符合要求的子字串 abcab, bcab, cab。
4. $i = 5$，$pos['a'] = 3, pos['b'] = 4, pos['c'] = 5$，min_idx = 3，有 4 組符合要求的子字串 abcabc, bcabc, cabc, abc。

答案為 10。

Python 程式碼

Runtime: 70 ms, beats 85.01%. Memory: 19.56 MB, beats 15.25%.

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        ans = 0
        pos = {'a': -1, 'b': -1, 'c': -1}
        for i, c in enumerate(s):
            pos[c] = i
            min_idx = min(pos.values())
            if min_idx != -1:
                ans += min_idx + 1
        return ans

C++ 程式碼

Runtime: 5 ms, beats 75.28%. Memory: 10.87 MB, beats 95.61%.

class Solution {
public:
    int numberOfSubstrings(string s) {
        int ans = 0, n = (int)s.size();  // 合格子字串數量，長度
        map<char, int> pos = {{'a', -1}, {'b', -1}, {'c', -1}};  // 最後一個 a, b, c 的索引值
        for(int i = 0; i < n; i++) {
            pos[s[i]] = i;  // 更新最後出現的位置
            int min_idx = min(pos['a'], min(pos['b'], pos['c']));  // a, b, c 最早出現的位置
            if (min_idx != -1) {  // a, b, c 都出現過
                ans += min_idx + 1;  // s[0] ~ s[min_idx] 的子字串都合法
            }
        }
        return ans;
    }
};