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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。