Problem: 1358. 包含所有三種字符的子字符串數目

思路

滑動窗口

解題過程

滑動窗口：使用左右指針 l 和 r 維護一個窗口，窗口內字符的頻次由 cnt 記錄。

右指針擴展：右指針 r 不斷右移，將字符加入窗口并更新頻率。

左指針收縮：當窗口內包含所有三個字符時，收縮左指針 l 并更新字符頻次，直到窗口不再滿足條件。

計數邏輯：每次右指針移動后，累加左指針的位置 l 到結果 ans 中。這是因為對于當前右邊界 r，所有以 l -1的位置為起點且以 r 為終點的子字符串都滿足條件。

Code

python

class Solution:def numberOfSubstrings(self, s: str) -> int:n = len(s)l = ans = 0cnt = defaultdict(int)for r, ch in enumerate(s):cnt[ch] += 1while len(cnt) >= 3:cnt[s[l]] -= 1if cnt[s[l]] == 0:del cnt[s[l]]l += 1ans += lreturn ans 

c++

class Solution {
public:int numberOfSubstrings(string s) {int n = s.length();int cnt[3]{0};int l = 0;int ans = 0;for(int r = 0; r < n; r ++){cnt[s[r]-'a'] ++;while(cnt[0] >= 1 && cnt[1] >= 1 && cnt[2] >= 1){cnt[s[l]-'a']--;l ++;}ans += l;}return ans;}
};

復雜度

• 時間復雜度: O(n)

• 空間復雜度: O(1)