计算C ++中给定字符串的所有子字符串的唯一字符

假设我们要定义一个称为countUniqueChars(s)的函数，该函数将返回s上唯一字符的数量，因此，如果s =“ HELLOWORLD”，则“ H”，“ E”，“ W”，“ R”，“ D”是唯一字符，因为它们仅在s中出现一次，因此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的大小

• 回答：= 0

• 定义大小为26的数组cnt

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• 在cnt [x-'A']的末尾插入-1

• x：= s [i]

• 如果cnt [x-'A']的大小等于0，则-

• 在cnt [x-'A']的末尾插入i

• 对于初始化i：= 0，当i <26时，更新（将i增加1），执行-

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

• ans：=添加(ans,temp)

• 忽略以下部分，跳至下一个迭代

• 如果cnt [i]的大小等于0，则-

• 在cnt [i]的末尾插入n

• 对于初始化j：= 1，当j <cnt [i]的大小时，更新（将j增加1），执行-

• 返回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