C++で正確にk個の異なる文字を含む部分文字列の数をカウントします

小文字のアルファベットのみと整数値kを含む文字列str[]が与えられます。目標は、正確にk個の異なる要素を持つstrの可能なサブストリングの数を見つけることです。

例

入力

str= ”pqr” k=2

出力

Count of number of substrings with exactly k distinct characters are: 2

説明

The substrings having exactly 2 distinct elements are: “pq”, “qr”.

入力

str= ”stristr” k=4

出力

Count of number of substrings with exactly k distinct characters are: 10

説明

The substrings having exactly 2 distinct elements are:
“stri”, “tris”, “rist”, “istr”, “stris”, “trist”, “ristr”, “strist”, “tristr”, “stristr”.

以下のプログラムで使用されるアプローチは次のとおりです −

このアプローチでは、文字列str内に英語のアルファベットの頻度を格納する配列array[26]を使用します。次に、2つのforループを使用してstrをトラバースします。サブストリングの場合、各文字が1回出現し、一意の文字のカウントをインクリメントします。そのサブストリングの最後で、カウントがkに等しい場合は、指定された条件に従ってサブストリングのカウントをインクリメントします。

• 文字列strを入力として受け取ります。

• 正の値を持つ整数kを取ります。

• 関数substring_k（string str、int length、int k）は、strとkを取り、正確にk個の異なる文字を持つサブストリングの数のカウントを返します。

• 初期カウントを0とします。

• 周波数配列配列[26]を取ります。

• i=0からi

• 部分文字列str[itoj]の一意の要素の数としてtempを取ります。

• array [str [j] −'a'] ==0の場合、この文字str[j]はこのサブストリングで初めて発生します。したがって、温度を上げます。

• ここで、array [str [j] −'a']++を使用して現在の文字のカウントをインクリメントします。

• tempがkに等しい場合は、カウントをインクリメントします。

• 気温がkを超える場合は、通勤を停止してループを中断します。

• すべてのループの最後に、結果としてカウントが返されます。

例

#include<bits/stdc++.h>
using namespace std;
int substring_k(string str, int length, int k){
   int count = 0;
   int array[26];
   for (int i = 0; i < length; i++){
      int temp = 0;
      memset(array, 0, sizeof(array));
      for (int j = i; j < length; j++){
         if(array[str[j] − 'a'] == 0){
            temp++;
         }
         array[str[j] − 'a']++;
         if (temp == k){
            count++;
         }
         if(temp > k){
            break;
         }
      }
   }
   return count;
}
int main(){
   string str = "abc";
   int length = str.length();
   int k = 1;
   cout<<"Count of number of substrings with exactly k distinct characters are: "<<substring_k(str, length, k);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of number of substrings with exactly k distinct characters are: 3