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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

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

方法一：枚举 + 二分

我们定义 a，b，c 都至少出现过一次的字符串为合法的字符串，否则为非法的字符串。

可以观察到一个性质：从下标 i 开始的所有子串，我们按顺序从前到后考虑，一定是前部分均非法，后部分均合法 ，简单来说，假设 [i,j] 的子串已经合法，那么 [i,j+1] 必然合法，如果 [i,j] 非法，那么 [i,j-1] 必然非法，这是很显然的。

通过这个性质我们知道对于下标 i 开始的所有子串，它的合法性是随下标具有单调性的（如果我们把非法字符串设为 0 ，合法字符串设为 1 ，那么从下标 i 开始的所有子串一定是 000011 这样的形式），所以我们就可以进行二分查找，找到第一个合法的子串的下标 j ，那么下标 i 开始的合法子串数就是 len(s)-j+1 了，最后的答案就是

\sum_{i=1}^{len(s)}len(s)-j+1

二分查找的时候需要判断子串是否合法，为了 O(1) 判断，我们需要预处理三个字符出现次数的前缀和数组，判断的时候直接 O(1) 差分查一下子串里 a，b，c 的个数即可判断。

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    #define N 50010
    int pre[3][N];
public:
    int numberOfSubstrings(string s) {
        int len=(int)s.length(),ans=0;
        pre[0][0]=pre[1][0]=pre[2][0]=0;
        for (int i=0;i<(int)s.length();++i){// 预处理前缀和数组
            for (int j=0;j<3;++j) pre[j][i+1]=pre[j][i];
            pre[s[i]-'a'][i+1]++;
        }
        for (int i=0;i<len;++i){
            int l=i+1,r=len,pos=-1;
            while (l<=r){
                int mid=l+((r-l)>>1);
                if (pre[0][mid]-pre[0][i]>0 && pre[1][mid]-pre[1][i]>0 && pre[2][mid]-pre[2][i]>0){// 都大于0说明a,b,c至少出现过一次，子串合法
                    r=mid-1;
                    pos=mid;
                }
                else l=mid+1;
            }
            if (~pos) ans+=len-pos+1;
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度：枚举每个下标需要 O(n) 的时间，n=s.length ，统计每个下标为起点里面套了一个二分需要 O(logn) 的时间，所以总时间复杂度为 O(nlogn) 。
  • 空间复杂度：为了二分里面判断是不是合法子串，需要额外提供一个前缀和数组，所以空间复杂度为 O(n) 。

方法二：双指针

针对上面发现的性质还可以继续深挖， 我们假设下标 i 开始第一个合法的字符串的末尾下标为 pos_i ，则可以知道：

pos_1\leq pos_2 \leq \cdots \leq pos_{len(s)

这说明了 pos_i 是单调不降的，如果我们已经得出了下标 i 开始的第一个合法字符串末尾的下标 pos_i ，则计算下标 i+1 的 pos_{i+1 的时候，我们就可以复用 [i+1,pos_i] 里的信息，即当前字符串里a，b，c出现的次数，再从 pos_i+1 开始往后延伸找到第一个符合条件的下标， 这就是我们常说的双指针算法。

维护两个指针 l 和 r ，以及 [l,r] 区间内 a，b，c 出现的次数。针对 l 找到第一个符合条件的 r 以后把答案加上 len(s)-r ，然后把 l 加一，减去 s[l] 字符的贡献，得出 [l+1,r] 里 a，b，c 出现的次数，然后再不断延伸 r 找第一个符合条件的合法字符串即可，这样我们就可以针对每一个下标找到对应的 pos_i ，最后的答案就是

\sum_{i=0}^{len(s)-1}len(s)-pos_i

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    int cnt[3];
public:
    int numberOfSubstrings(string s) {
        int len=(int)s.length(),ans=0;
        cnt[0]=cnt[1]=cnt[2]=0;
        for (int l=0,r=-1;l<len;){
            while (r<len && !(cnt[0]>=1 && cnt[1]>=1 && cnt[2]>=1)){
                if (++r==len) break;
                cnt[s[r]-'a']++;
            }
            ans+=len-r;
            cnt[s[l++]-'a']--;
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度：两个指针各移动了 n 次，所以时间复杂度为 O(n) ，n=s.length 。
  • 空间复杂度：只需要常数的空间记录当前三个字符的出现次数，所以空间复杂度为 O(1) 。
 Comments
On this page
1358-包含所有三种字符的子字符串数目