blob: 8c5938c47a9d757da1d6b7a4433b6d647d5b69dd (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
// 2262. Total Appeal of A String
#include "leetcode.h"
/*
* the appeal of a string is the number of distinct characters found in the
* string. for example, the appeal of "aabca" is 3 because it has 3 distinct
* characters 'a', 'b' and 'c'. given a string 's', return the total appeal of
* along long its substrings. a substring is a contiguous sequence of characters
* within a string.
*/
long long appealSum(char *s) {
long long ans = 0;
int n = strlen(s);
int *dp = (int *)calloc(26, sizeof(int));
for (int i = 0; i < n; i++) {
ans += (long long)(i + 1 - dp[s[i] - 'a']) * (long long)(n - i);
dp[s[i] - 'a'] = i + 1;
}
free(dp);
return ans;
}
int main() {
char *s1 = "aabca", *s2 = "code";
printf("%lld\n", appealSum(s1)); // expect: 28
printf("%lld\n", appealSum(s2)); // expect: 20
}
|