数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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，
返回(a mod m) + (b mod m)
定义一个函数mul()，它将接收a, b，
返回(a mod m) * (b mod m)
从主方法中执行以下操作：
n := s的大小
ans := 0
定义一个大小为26的数组cnt
对于初始化i := 0，当i < n时，更新（i增加1），执行：
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 < cnt[i]的大小时，更新（j增加1），执行：
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
542 次查看
