数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中不包含集合 {‘a’, ‘b’, ‘c’} 中所有字符的子字符串的计数
给定一个字符串 str[]，其中只包含 ‘a’，‘b’ 和 ‘c’。目标是找到 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’) 的先前索引。只需从计数中减去其他两个字符的最小索引，因为我们知道我们正在移除该字符以在子字符串中包含当前字符，以便它不包含所有三个字符。
将字符串 str 作为字符数组。
函数 sub_without_all(char str[], int size) 获取一个字符串，它的长度并返回不包含 ‘a’，‘b’ 和 ‘c’ 所有字符的子字符串的计数。
获取初始计数 size*(size+1)/2，表示 str[] 所有可能的子字符串的数量。
获取变量 a、b、c 以存储 str[] 中 ‘a’，‘b’，‘c’ 的最后一个索引。全部初始化为 0。
使用 for 循环遍历 str[]，从 i=0 到 i<size。
如果 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
210 次浏览
