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)