C++で最大k回出現する各文字の部分文字列をカウントします

文字列strが与えられます。目標は、各文字が最大k回出現するstr内のサブストリングの数をカウントすることです。たとえば、入力が「abc」でk =1の場合、部分文字列は「a」、「b」、「c」、「ab」、「bc」、「abc」になります。

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

入力 − str =” abaefgf”

出力 −最初と最後の文字が同じ部分文字列の数は＆mmius;です。 9

説明 −部分文字列は

“a”, “b”, “a”, “e” ,”f”, “g”, “f”, “aba”, “fgf”. Total 9.

入力 − str =” abcdef”

出力 −最初と最後の文字が同じ部分文字列の数は次のとおりです。6

説明 −部分文字列は-

“a” , “b” , “c”, “d”, “e” ,”f”. Total 6

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

与えられた問題を解決するための複数のアプローチ、すなわちナイーブなアプローチと効率的なアプローチがあります。それでは、最初に素朴なアプローチを見てみましょう。すべての長さの部分文字列を関数check（）に渡します。その部分文字列が同じ文字で開始および終了する場合は、カウントを増やします。

• 文字列strを取ります。長さをstr.size（）として計算します。

• 関数check（string str）は、部分文字列strを受け取り、最初と最後の文字が同じかどうかをチェックします。 （str [0] ==str [length-1]）。 trueの場合、1を返します。

• 関数check_Start_End（string str、int length）は、strとその長さを入力として受け取り、同じ文字で開始および終了するstrのサブストリングの数を返します。

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

• 2つのforループを使用してstrをトラバースします。 i=0からi

• すべての長さのsubstr（i、j）を使用して、すべての部分文字列を取得します。各サブ文字列をcheck（）に渡します。 1を返す場合は、カウントをインクリメントします。

• 両方のforループの終わりに、カウントには同じ開始文字と終了文字を持つstrのサブストリングがいくつかあります。

• 目的の結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
int count_k(string str, int len, int k){
   int count = 0;
   int arr[26];
   for (int i = 0; i < len; i++){
      memset(arr, 0, sizeof(arr));
      for (int j = i; j < len; j++){
         arr[str[j] - 'a']++;
         if (arr[str[j] - 'a'] <= k)
            { count++; }
         else
            { break; }
      }
   }
   return count;
}
int main(){
   string str = "bbddehj";
   int k = 1;
   int length = str.length();
   cout<<"Count of substrings with each character occurring at most k times are: "<<count_k(str,
length, k);
   return 0;
}

出力

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

Count of substrings with each character occurring at most k times are: 14