我们得到一个只包含 'a'、'b' 和 'c' 的字符串 str[]。目标是找到 str[] 的子字符串，使得所有三个字符都不是该子字符串的一部分。对于任何字符串 str，子字符串可以是“a”、“b”、“c”、“abb”、“bba”、“bc”、“ca”、“ccc”，但不能是“abc”、“bcca”、“ cab”，因为它们有 'a'、'b' 和 'c'，所有三个。
让我们通过例子来理解。
输入- str[] = “aabc”
输出- 不包含集合 {'a', 'b', 'c'} 中所有字符的子字符串的计数为 - 8
说明- 子字符串将是：“a”、“a”、“b”、“c”、“aa”、“ab”、“bc”、“aab”
输入- str[] = “abcabc”
输出- 不包含集合 {'a', 'b', 'c'} 中所有字符的子字符串的计数为 - 11
说明- 子串将是：“a”、“b”、“c”、“a”、“b”、“c”、“ab”、“bc”、“ca”、“ab”、“bc”
在这种方法中，我们知道具有 n 个字符的字符串的子串总数为 n*(n+1)/2。
我们现在将遍历字符串并针对每种类型的字符 'a'、'b' 或 'c'。我们将检查其他两个字符 ('b','c')、('c','a') 和 ('a', 'b') 的先前索引。只需从 count 中减去其他两个的最小索引，因为我们知道我们正在删除该字符以将当前字符包含在子字符串中，以便它不包含所有三个。
将字符串 str 作为字符数组。
函数 sub_without_all(char str[], int size) 接受一个字符串，它的长度并返回不包含 'a'、'b' 和 'c' 的子字符串的计数。
对于 str[] 的所有可能子串的数量，取初始计数 size*(size+1)/2。
取变量 a,b,c 来存储 str[] 中 'a', 'b', 'c' 的最后一个索引。全部初始化为 0。
使用 for 循环从 i=0 到 i<size 遍历 str[]。
如果 str[i]=='a' 更新 'a' 的索引为 a=i+1。从计数中减去 'b' 或 'c' 的索引的最小值以在子字符串中包含 'a'。从计数中减去 b,c 中的最小值。
对 str[i]=='b' 或 str[i]=='c' 执行与上一步类似的操作。
最后，我们算作 str[] 的子字符串，其中没有同时包含所有三个字符。
返回计数作为结果。
#include <bits/stdc++.h>
using namespace std;
int sub_without_all(char str[], int size){
int update_size = size * (size + 1);
int count = update_size / 2;
int a, b, c;
a = b = c = 0;
for (int i = 0; i < size; i++){
if (str[i] == 'a'){
a = i + 1;
count -= min(b, c);
}
else if (str[i] == 'b'){
b = i + 1;
count -= min(a, c);
}
else{
c = i + 1;
count -= min(a, b);
}
}
return count;
}
int main(){
char str[] = "abcabbc";
int size = strlen(str);
cout<<"Count of sub-strings that do not contain all the characters from the set {‘a’, ‘b’, ‘c’} at
the same time are: "<<sub_without_all(str, size);
return 0;
}输出结果如果我们运行上面的代码，它将生成以下输出 -
Count of sub-strings that do not contain all the characters from the set {‘a’, ‘b’, ‘c’} at the same time are: 15