日期: 2026年6月30日

目标

给你一个字符串 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

说明：

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

思路

有一个字符串只包含三个字符 a b c，求这三个字符至少出现一次的子串个数。

直接的想法是计算这三个字符出现次数的前缀和，然后使用滑动窗口。使用前缀和来判断窗口内的子串是否满足条件，如果 [l, r] 满足条件，那么 [l, r ~ n - 1] 也满足条件。

判断字符是否至少出现一次可以不用前缀和，使用三个变量记录它们上次出现的下标，如果小于左端点则用 -1 标记。

代码

/**
 * @date 2026-06-30 9:14
 */
public class NumberOfSubstrings1358 {

    public int numberOfSubstrings(String s) {
        int n = s.length();
        int a = -1, b = -1, c = -1;
        int l = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'a') {
                a = i;
            } else if (s.charAt(i) == 'b') {
                b = i;
            } else {
                c = i;
            }
            while (a >= 0 && b >= 0 && c >= 0) {
                res += n - i;
                if (a <= l) {
                    a = -1;
                } else if (b <= l) {
                    b = -1;
                } else if (c <= l) {
                    c = -1;
                }
                l++;
            }
        }
        return res;
    }

}

性能