LEETCODE 1358. Number of Substrings Containing All Three Characters 解题思路分析

题目大意：

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

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1358

解题思路分析：

看到这种求子串的问题，我们应该下意识想到使用双指针来解题。我们定义左右两个指针来代表当前子串区间范围。另外定义一个数组来记录每种字符在区间内的个数。开始时，左右指针均为0，我们先循环右指针（扩大区间范围），当左右指针范围内三种字符的个数都大于0时，当前区间内子串即是一个符合要求的答案，另外，因为当前区间为合理区间，那么当前左指针，与右指针到字符串尾部组成的所有子串都应该是合理区间，因此此时找到的合理子串数应该是字符串长度减去右指针。此时开始移动左指针，每移动一步（缩小区间范围），如果区间内字符个数仍然符合要求，继续添加符合条件的区间个数（字符串长度减去右指针）到返回结果，直到区间内三种字符中某个字符个数为0为止，这时返回继续移动右指针，重复上述步骤直到遍历完整个字符串。

实现代码：

public int numberOfSubstrings(String s) {
    // 记录区间内a，b，c三中字符个数
    int[] count = new int[3];
    // 左右指针
    int left=0,right=0;
    // 返回结果
    int res=0;
    // 为了提高效率，将字符串转为数组
    char[] arr = s.toCharArray();
    // 循环
    while(right<arr.length&&left<arr.length){
        // 将右指针指向的字符个数加一
        count[arr[right]-'a']++;
        // 如果当前区间内三种字符个数均大于0
        while(count[0]>0&&count[1]>0&&count[2]>0){
            // 添加合理区间个数到返回结果
            res+=(s.length()-right);
            // 左指针指向字符个数减一
            count[arr[left]-'a']--;
            // 左指针向右移动一格
            left++;
        }
        // 右指针向右移动一格
        right++;
    }
    return res;
}

本题解法执行时间为7ms。

Runtime: 7 ms, faster than 83.49% of Java online submissions for Number of Substrings Containing All Three Characters.

Memory Usage: 40.8 MB, less than 100.00% of Java online submissions for Number of Substrings Containing All Three Characters.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1358-number-of-substrings-containing-all-three-characters-解题思路分析/