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

思路：

1. 由于字符串只有三个字母，易知包含三种字符a, b ,c中任意一个字符的子串 ，应该是字符串的所有字串
2. 例如aaacb，就是5+4+3+2+1
3. 三个都出现过至少一次的 = 包含三种字符a, b ,c中任意一个字符的所有子串 - 包含两个字符中任意一个字符的所有子串
4. 描述不太清晰 ，例如aacb：
5. 包含三种字符a, b ,c中任意一个字符的所有子串：a,aa,a,aac,ac,c,aacb,acb,cb,b
6. 包含两个字符中任意一个字符的所有子串：a,aa,a,aac,ac,c,cb,b
7. 相当于分解问题的思路，挺有用的
   代码如下：

def numberOfSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        def findmax(s):
            win = collections.Counter()
            l,count = 0,0
            res = 0
            for r in range(len(s)):
                win[s[r]] += 1
                if win[s[r]] == 1:
                    count += 1
                while count == 3:
                    win[s[l]] -= 1
                    if win[s[l]] == 0:
                        count -= 1
                    l += 1
                res += r-l+1
            return res
        res = (len(s)**2 + len(s))/2
        return res - findmax(s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

解法二
找到一个满足条件的之后，在他之后的所有字符都满足条件
所以加上它本身就是len(s)-r
之后移动左指针，直到它不符合参考：
https://leetcode.cn/problems/number-of-substrings-containing-all-three-characters/solution/si-kao-de-guo-cheng-bi-da-an-zhong-yao-xiang-xi-tu/

def numberOfSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        win = collections.Counter()
        l,count = 0,0
        res = 0
        for r in range(len(s)):
            win[s[r]] += 1
            if win[s[r]] == 1:
                count += 1
            while count == 3:
                res += len(s)-r
                win[s[l]] -= 1
                if win[s[l]] == 0:
                    count -= 1
                l += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19