1358. 包含所有三种字符的子字符串数目 Medium

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。

请你返回 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

解题思路

输入：一个只包含 a b c 字符的字符串 s

输出：返回a b c 都至少出现过一次的子字符串数目

本题属于典型的 可变长度滑动窗口类型 问题。

我们需要用到一个 map 来记录窗口内的 a b c出现个数

我们以左边界为起点移动右边界，每次都更新 map 里面的 a b c 出现次数

当满足条件的时候说明后面不论出现什么都会满足 a b c至少出现一次，更新答案 ans += len(s) - right

然后我们再移动左边界向右扩展，直到不满足为止我们再次移动右边界找下一个合法窗口

本体的难点在于要理解当窗口满足条件时候，后续不论出现什么字符都是符合条件的，所以可以直接更新答案 ans += len(s) - right

代码实现

python

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        left = 0               # 滑动窗口左边界
        ans = 0                # 用于统计满足条件的子串数量
        countMap = { 'a': 0, 'b': 0, 'c': 0 }  # 记录 a、b、c 在当前窗口中的出现次数

        # 遍历字符串的每个字符，right 为滑动窗口右边界
        for right in range(len(s)):
            # 将当前字符加入窗口，并更新其出现次数
            countMap[s[right]] += 1

            # 当窗口中 a、b、c 都至少出现一次时，进行统计
            while countMap['a'] > 0 and countMap['b'] > 0 and countMap['c'] > 0:
                # 说明从当前 left 到字符串末尾的所有以 right 结尾的子串都是合法的
                # 因为只要当前窗口满足条件，right 再往右扩展仍然满足条件
                ans += len(s) - right

                # 尝试收缩窗口：将左边界的字符移出窗口
                countMap[s[left]] -= 1
                left += 1  # 左边界右移

        return ans

javascript

/**
 * @param {string} s
 * @return {number}
 */
var numberOfSubstrings = function(s) {
    const map = { a: 0, b: 0, c: 0 };

    let left = 0;
    let ans = 0;

    for (let right = 0; right < s.length; right++) {
        map[s[right]] ++;

        while (map['a'] > 0 && map['b'] > 0 && map['c'] > 0) {
            ans += s.length - right;
            map[s[left]] --;
            left ++;
        }
    }

    return ans;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

1358 国际版

1358 中文版