[LeetCode] 1358. Number of Substrings Containing All Three Characters

Given a string s consisting only of characters a, b and c.

Return the number of substrings containing at least one occurrence of all these characters a, b and c.

Example 1:
Input: s = “abcabc”
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are “abc”, “abca”, “abcab”, “abcabc”, “bca”, “bcab”, “bcabc”, “cab”, “cabc” and “abc” (again).

Example 2:
Input: s = “aaacb”
Output: 3
Explanation: The substrings containing at least one occurrence of the characters a, b and c are “aaacb”, “aacb” and “acb”.

Example 3:
Input: s = “abc”
Output: 1

Constraints:
3 <= s.length <= 5 x 10^4
s only consists of a, b or c characters.

包含所有三种字符的子字符串数目。

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

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

思路

不难想到这是一道滑动窗口的题，因为窗口内的子串需要满足 abc 三个字母同时出现，但是这道题不太容易思考的地方在于怎么计算满足题意的子串数量。

对于大部分的滑动窗口题，我们一开始还是移动右指针 end 来看看左右指针之间 [start, end] 的部分是否满足题意，就这道题而言，移动右指针，同时统计左右指针之间 abc 三个字母各自的出现次数。当 abc 三个字母的出现次数都分别大于 0 时，我们就可以考虑移动左指针，直到不满足题意的子串。

注意当我们第一次满足 abc 三个字母的出现次数都分别大于 0 时 这个条件的时候，我们就可以尝试移动左指针 start 了。此时 [start, end] 之间的子串都是满足题意的，直到我们移动左指针 start 导致 abc 中某个字母的出现次数变为 0。所以在 start 指针移动过程中，结果是累加的。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int numberOfSubstrings(String s) {
        int n = s.length();
        int start = 0;
        int end = 0;
        int res = 0;
        int[] map = new int[3];
        while (end < n) {
            char c1 = s.charAt(end);
            map[c1 - 'a']++;
            end++;
			// 只有abc出现次数都大于0的时候才移动左指针
            while (map[0] > 0 && map[1] > 0 && map[2] > 0) {
                char c2 = s.charAt(start);
                map[c2 - 'a']--;
                start++;
            }
			// [左指针及其左边, 右指针] 都是满足题意的子串
			// 所以个数是 start
            res += start;
        }
        return res;
    }
}

相关题目

1358. Number of Substrings Containing All Three Characters
3325. Count Substrings With K-Frequency Characters I