题目描述

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

请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。

样例

输入：s = "abcabc"
输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为
"abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc"
（相同字符串算多次）。

输入：s = "aaacb"
输出：3
解释：包含 a，b 和 c 各至少一次的子字符串为 "aaacb", "aacb" 和 "acb"。

输入：s = "abc"
输出：1

限制

• 3 <= s.length <= 5 * 10^4
• s 只包含字符 a，b 和 c。

算法

(双指针) $O(n)$

1. 我们不妨考虑有多少个子串不满足以上条件。
2. 对于每一个以位置 i 结尾的子串，我们试图找到一个最小的 last，满足 [last, i] 区间不满足条件。容易发现，如果 [last, i] 不满足条件，那么对于 i + 1 来说，last 的位置不可能更小。所以，last 是随着 i 单调不减的。
3. 维护 last 和 i 两个位置，如果 [last, i] 区间满足条件，则令 last++，直到不满足条件为止。然后 i 位置贡献的不满足条件的答案就是 i - last + 1。
4. 最终满足条件的答案就是 n * (n + 1) / 2 - ans。

时间复杂度

• 每个位置最多遍历两次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    #define LL long long
    int numberOfSubstrings(string s) {
        int n = s.length();
        int a = 0, b = 0, c = 0;

        LL ans = 0;
        for (int i = 0, last = 0; i < n; i++) {
            if (s[i] == 'a') a++;
            else if (s[i] == 'b') b++;
            else c++;

            while (last < i && (a > 0 && b > 0 && c > 0)) {
                if (s[last] == 'a') a--;
                else if (s[last] == 'b') b--;
                else c--;
                last++;
            }
            ans += i - last + 1;
        }

        return (LL)(n) * (n + 1) / 2 - ans;
    }
};