C ++で同時にセット{‘a’、‘b’、‘c’}のすべての文字を含まないサブ文字列の数

「a」、「b」、「c」のみを含む文字列str[]が与えられます。目標は、3つの文字すべてがその部分文字列の一部にならないようにstr[]の部分文字列を見つけることです。任意の文字列strの場合、サブ文字列は「a」、「b」、「c」、「abb」、「bba」、「bc」、「ca」、「ccc」である可能性がありますが、「abc」、「bcca」、「 cab」は、「a」、「b」、「c」の3つすべてを備えているためです。

例を挙げて理解しましょう。

入力 − 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」をトラバースします。他の2つの文字（「b」、「c」）、（「c」、「a」）、および（「a」、「b」）の以前のインデックスを確認します。他の2つの最小インデックスをカウントから差し引くだけです。これは、その文字を削除して現在の文字をサブストリングに含め、3つすべてが含まれないようにするためです。

• 文字列strを文字配列として使用します。

• 関数sub_without_all（char str []、int size）は文字列を受け取り、その長さで、「a」、「b」、「c」をすべて一緒に含まない部分文字列の数を返します。

• str []のすべての可能なサブストリングの数について、初期カウントサイズ*（size + 1）/2を取ります。

• 変数a、b、cを使用して、「a」、「b」、「c」の最後のインデックスをstr[]に格納します。すべてを0で初期化します。

• forループを使用してstr[]をi=0からiまでトラバースします。

• str [i] ==’a’の場合、‘a’のインデックスをa =i+1として更新します。カウントから「b」または「c」のインデックスの最小値を減算して、サブストリングに「a」を含めます。カウントから最小のb、cを引きます。

• str [i] ==’b’またはstr [i] ==’c’の前の手順と同様に行います。

• 最後に、3文字すべてを一度に含まない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