Leetcode 1358:包含所有三种字符的子字符串数目(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1358:包含所有三种字符的子字符串数目(超详细的解法!!!)

in leetcode with 0 comment

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

提示:

解题思路

这个问题可以采用滑动窗口处理,我们通过lr控制窗口的左右边界,首先r不断向右移动,直到窗口[l,r]中包含了三种字符。对于第一个例子

a b c a b c
l   r

此时字符串s[l:k]满足条件,其中r<k<=n,总共包含len(s)-r个字符串。接着我们将l右移,直到窗口[l,r]不再包含了三种字符。

a b c a b c
  l r

此时再继续移动r直达再次满足条件。最后代码如下:

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        res, l, cnt = 0, -1, {c : 0 for c in 'abc'}
        
        for r, c in enumerate(s):
            cnt[c] += 1
            while all(cnt.values()):
                res += len(s) - r
                l += 1
                cnt[s[l]] -= 1
        return res

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses