class Solution {
public:
int numberOfSubstrings(string s) {
}
};
1358. 包含所有三种字符的子字符串数目
给你一个字符串 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^4s 只包含字符 a，b 和 c 。原站题解
python3 解法, 执行用时: 144 ms, 内存消耗: 15 MB, 提交时间: 2022-12-17 16:03:54
'''
遍历整个字符串，每次迭代时加上以当前字符结尾的合法字符串数量。下面只需要每次计算这个数量即可
每次更新，'a','b','c',三个字符所在的索引最右侧位置，三个字符位置的最小值即为当前字符结尾的最短字符串的最左端，记这个字符串为A。
从字符串A向左可以扩充的字符串数量恰为A的最左端索引。
'''
class Solution:
def numberOfSubstrings(self, s: str) -> int:
cnt_ch = {'a': 0, 'b': 0, 'c': 0}
cnt = 0
for i in range(len(s)):
cnt_ch[s[i]] = i + 1
cnt += min(cnt_ch['a'], cnt_ch['b'], cnt_ch['c'])
return cnt
python3 解法, 执行用时: 280 ms, 内存消耗: 15.3 MB, 提交时间: 2022-12-17 16:01:09
class Solution:
def numberOfSubstrings(self, s: str) -> int:
if len(s) < 3: return 0
head, tail = 0, 2
n = len(s)
ans = 0
while head < n - 2:
tmp = s[head: tail + 1]
if 'a' in tmp and 'b' in tmp and 'c' in tmp:
ans += n - tail
head += 1
else:
tail += 1
if tail == n: break
return ans
java 解法, 执行用时: 11 ms, 内存消耗: 41.5 MB, 提交时间: 2022-12-17 16:00:33
class Solution {
public int numberOfSubstrings(String s) {
int answer=0;
//abc 的计数
int[] count=new int[3];
//窗口左沿
int start=0;
//窗口右沿
for(int end=0;end<s.length();end++){
char charAtEnd=s.charAt(end);
count[charAtEnd-'a']++;
while(count[0]>=1 && count[1]>=1 && count[2]>=1){
answer+=s.length()-end;
char charAtStart=s.charAt(start);
count[charAtStart-'a']--;
start++;
}
}
return answer;
}
}
cpp 解法, 执行用时: 48 ms, 内存消耗: 8.9 MB, 提交时间: 2022-12-17 15:59:51
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;
}
};
cpp 解法, 执行用时: 16 ms, 内存消耗: 8.3 MB, 提交时间: 2022-12-17 15:59:29
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;
}
};