Formatted question description: https://leetcode.ca/all/1915.html

# 1915. Number of Wonderful Substrings

## Level

Medium

## 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:

- “
**a**ba” -> “a” - “a
**b**a” -> “b” - “ab
**a**” -> “a” - “
**aba**” -> “aba”

**Example 2:**

**Input:** word = “aabb”

**Output:** 9

**Explanation:** The nine wonderful substrings are underlined below:

- “
**a**abb” -> “a” - “
**aa**bb” -> “aa” - “
**aab**b” -> “aab” - “
**aabb**” -> “aabb” - “a
**a**bb” -> “a” - “a
**abb**” -> “abb” - “aa
**b**b” -> “b” - “aa
**bb**” -> “bb” - “aab
**b**” -> “b”

**Example 3:**

**Input:** word = “he”

**Output:** 2

**Explanation:** The two wonderful substrings are underlined below:

- “
**h**e” -> “h” - “h
**e**” -> “e”

**Constraints:**

`1 <= word.length <= 10^5`

`word`

consists of lowercase English letters from`'a'`

to`'j'`

.

## Solution

Use bit manipulation. The number of occurrences of each letter can be represented as a bit such that 1 represents an odd number of times and 0 represents an even number of times. For ten letters, the value can be represented with ten bits, in range [0, 1023]. Loop over `word`

and for each index, get the value at the index and update the map, which stores each value’s number of occurrences (here “values” means “keys” of the map). Then loop over all pairs in the map such that the two keys have at most 1 bit that is different, and calculate the number of wonderful substrings.

```
class Solution {
public long wonderfulSubstrings(String word) {
long wonderful = 0;
final int TOTAL = 1 << 10;
long[] map = new long[TOTAL];
map[0] = 1L;
int value = 0;
int length = word.length();
for (int i = 0; i < length; i++) {
char c = word.charAt(i);
int index = c - 'a';
value ^= (1 << index);
map[value]++;
}
for (int i = 0; i < TOTAL; i++) {
wonderful += map[i] * (map[i] - 1) / 2;
for (int j = 1; j <= i; j <<= 1) {
if ((i & j) == j)
wonderful += map[i] * map[i - j];
}
}
return wonderful;
}
}
```