在 C++ 中不包含集合 {'a', 'b', 'c'} 中所有字符的子字符串的计数

2023-06-21 14:23:04 201

我们得到一个只包含'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(charstr[],intsize)接受一个字符串，它的长度并返回不包含'a'、'b'和'c'的子字符串的计数。

对于str[]的所有可能子串的数量，取初始计数size*(size+1)/2。

取变量a,b,c来存储str[]中'a','b','c'的最后一个索引。全部初始化为0。

使用for循环从i=0到i

如果str[i]=='a'更新'a'的索引为a=i+1。从计数中减去'b'或'c'的索引的最小值以在子字符串中包含'a'。从计数中减去b,c中的最小值。

对str[i]=='b'或str[i]=='c'执行与上一步类似的操作。

最后，我们算作str[]的子字符串，其中没有同时包含所有三个字符。

返回计数作为结果。

示例

#include 
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: "<输出结果
如果我们运行上面的代码，它将生成以下输出-
Count of sub-strings that do not contain all the characters from the set {‘a’, ‘b’, ‘c’} at the same time are: 15

在 C++ 中不包含集合 {'a', 'b', 'c'} 中所有字符的子字符串的计数

下面程序中使用的方法如下

示例

热门推荐

随机推荐