Description#
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 English 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 occurrence separately.
A substring is a contiguous sequence of characters in a string.
Example 1:
Input: word = "aba"
Output: 4
Explanation: The four wonderful substrings are underlined below:
- "aba" -> "a"
- "aba" -> "b"
- "aba" -> "a"
- "aba" -> "aba"
Example 2:
Input: word = "aabb"
Output: 9
Explanation: The nine wonderful substrings are underlined below:
- "aabb" -> "a"
- "aabb" -> "aa"
- "aabb" -> "aab"
- "aabb" -> "aabb"
- "aabb" -> "a"
- "aabb" -> "abb"
- "aabb" -> "b"
- "aabb" -> "bb"
- "aabb" -> "b"
Example 3:
Input: word = "he"
Output: 2
Explanation: The two wonderful substrings are underlined below:
- "he" -> "h"
- "he" -> "e"
Constraints:
1 <= word.length <= 105word consists of lowercase English letters from 'a' to 'j'.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def wonderfulSubstrings(self, word: str) -> int:
cnt = Counter({0: 1})
ans = st = 0
for c in word:
st ^= 1 << (ord(c) - ord("a"))
ans += cnt[st]
for i in range(10):
ans += cnt[st ^ (1 << i)]
cnt[st] += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public long wonderfulSubstrings(String word) {
int[] cnt = new int[1 << 10];
cnt[0] = 1;
long ans = 0;
int st = 0;
for (char c : word.toCharArray()) {
st ^= 1 << (c - 'a');
ans += cnt[st];
for (int i = 0; i < 10; ++i) {
ans += cnt[st ^ (1 << i)];
}
++cnt[st];
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
long long wonderfulSubstrings(string word) {
int cnt[1024] = {1};
long long ans = 0;
int st = 0;
for (char c : word) {
st ^= 1 << (c - 'a');
ans += cnt[st];
for (int i = 0; i < 10; ++i) {
ans += cnt[st ^ (1 << i)];
}
++cnt[st];
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| func wonderfulSubstrings(word string) (ans int64) {
cnt := [1024]int{1}
st := 0
for _, c := range word {
st ^= 1 << (c - 'a')
ans += int64(cnt[st])
for i := 0; i < 10; i++ {
ans += int64(cnt[st^(1<<i)])
}
cnt[st]++
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| function wonderfulSubstrings(word: string): number {
const cnt: number[] = new Array(1 << 10).fill(0);
cnt[0] = 1;
let ans = 0;
let st = 0;
for (const c of word) {
st ^= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
ans += cnt[st];
for (let i = 0; i < 10; ++i) {
ans += cnt[st ^ (1 << i)];
}
cnt[st]++;
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| /**
* @param {string} word
* @return {number}
*/
var wonderfulSubstrings = function (word) {
const cnt = new Array(1024).fill(0);
cnt[0] = 1;
let ans = 0;
let st = 0;
for (const c of word) {
st ^= 1 << (c.charCodeAt() - 'a'.charCodeAt());
ans += cnt[st];
for (let i = 0; i < 10; ++i) {
ans += cnt[st ^ (1 << i)];
}
cnt[st]++;
}
return ans;
};
|
