blob: 15bca293be969572433850c399a11980eb0d1335 (
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
29
30
31
32
33
34
35
36
37
38
|
// 1915. Number of Wonderful Substrings
#include "leetcode.h"
/*
* a wonderful string is a string where at most one letter appears an odd number
* of times. for example "ccjjc" and "abab" are wonderful, but "ab" is not.
* given a string 'word' that consists of the first ten lowercase letters ('a'
* through 'j') return the number of wonderful non-empty substrings in 'word'.
* if the same substring appears multiple times in 'word', then count each
* occurence separately. a substring is a contiguous sequence of character in a
* string.
*/
long long wonderfulSubstrings(char *word) {
int n = strlen(word), state = 0;
int *cnt = (int *)calloc(1 << 10, sizeof(int));
cnt[0] = 1;
long long ans = 0;
for (int i = 0; i < n; i++) {
int k = word[i] - 'a';
state ^= (1 << k);
ans += cnt[state];
for (int j = 0; j < 10; j++) {
int j_state = state ^ (1 << j);
ans += cnt[j_state];
}
cnt[state]++;
}
free(cnt);
return ans;
}
int main() {
char *w1 = "aba", *w2 = "aabb", *w3 = "he";
printf("%lld\n", wonderfulSubstrings(w1)); // expect: 4
printf("%lld\n", wonderfulSubstrings(w2)); // expect: 9
printf("%lld\n", wonderfulSubstrings(w3)); // expect: 2
}
|