C++で特定の文字列のすべてのサブ文字列の一意の文字をカウントします

sの一意の文字数を返すcountUniqueChars（s）という関数を定義するとします。したがって、s ="HELLOWORLD"の場合、 "H"、 "E"、 「W」、「R」、「D」は、sに1回しか表示されないため、一意の文字です。したがって、countUniqueChars（s）=5です。

ここで、文字列sが与えられた場合のこの問題について、countUniqueChars（t）の合計を見つける必要があります。ここでtはsの部分文字列です。 （ここでは、いくつかの部分文字列を繰り返すことができるため、この場合、繰り返される部分文字列もカウントする必要があります。）

答えは非常に大きくなる可能性があるため、10 ^ 9+7を法として答えを返すことができます。

したがって、入力が「HELLOWORLD」のような場合、出力は128

これを解決するには、次の手順に従います-

• 関数add（）を定義します。これには、a、b、

  が必要です。

• return（a mod m）+（b mod m）

• 関数mul（）を定義します。これにはa、b、

  が必要です。

• return（a mod m）*（b mod m）

• メインの方法から、次のようにします-

• n：=sのサイズ

• ans：=0

• サイズ26の配列cntを定義します

• 初期化i：=0の場合、i

  • x：=s [i]

  • cnt [x-'A']のサイズが0と同じ場合、-

    • cnt [x-'A']

      の最後に-1を挿入します

  • cnt [x-'A']

    の最後にiを挿入します

• 初期化i：=0の場合、i <26の場合、更新（iを1増やします）、実行-

  • cnt [i]のサイズが0と同じ場合、-

    • 次の部分を無視し、次の反復にスキップします

  • cnt [i]

    の最後にnを挿入します

  • 初期化j：=1の場合、j

    • temp：=mul（cnt [i、j] --cnt [i、j --1]、cnt [i、j + 1] --cnt [i、j]）

    • ans：=add（ans、temp）

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
   public:
   lli add(lli a, lli b){
      return (a % m) + (b % m);
   }
   lli mul(lli a, lli b){
      return (a % m) * (b % m);
   }
   int uniqueLetterString(string s) {
      int n = s.size();
      int ans = 0;
      vector<int> cnt[26];
      for (int i = 0; i < n; i++) {
         char x = s[i];
         if (cnt[x - 'A'].size() == 0) {
            cnt[x - 'A'].push_back(-1);
         }
         cnt[x - 'A'].push_back(i);
      }
      for (int i = 0; i < 26; i++) {
         if (cnt[i].size() == 0)
         continue;
         cnt[i].push_back(n);
         for (int j = 1; j < cnt[i].size() - 1; j++) {
            lli temp = mul(cnt[i][j] - cnt[i][j - 1], cnt[i][j +
            1] - cnt[i][j]);
            ans = add(ans, temp);
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.uniqueLetterString("HELLOWORLD"));
}

入力

"HELLOWORLD"

出力

128