当前位置：首页 > article >正文

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

article 2025/1/26 22:21:50

题目如下
在这里插入图片描述
数据范围

这道题同样是不定长的滑动窗口，有意思的地方在于我们只需要找到每一个"最小合法的子串"对应的左右端点就行。什么意思呢？
题目要求合法子串必须包含abc 那么对于s = "abcaaaaaa"来说 sub = "abc"或者sub = "bca"就是最小合法子串，
根据题意只要子串包含"最小合法子串"那么都是合法的子串对于上面的s来说abc是对的 abca abcaa....都是对的而包含abc这个子串的大子串有n - i个(且计算了abc本身)
即s的长度减去右端点的小标,读者可以自己数数。通过不断移动固定左端点向右寻找这样的"最小合法子串"通过上面的公式不断相加就能得到答案。

通过代码

class Solution {
public:
    int numberOfSubstrings(string s) {
        int c[3];
        int n = s.size();
        int count = 0;
         c[0]=c[1]=c[2]=0;
        for(int i = -1,j = 0;j < n;){
                while(i < n &&!(c[0] != 0 && c[1] != 0 && c[2] != 0)){
                        if(++i == n)break;
                        c[s[i] - 'a']++;
                        
                }
                if(c[0] != 0 && c[1] != 0 && c[2] != 0){
           
                    count += n - i;
                }
                c[s[j++] - 'a']--;
            }
        
        return count;
    }
};