aboutsummaryrefslogtreecommitdiff
path: root/total_appeal_string.c
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
}