# Number of Wonderful Substrings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-wonderful-substrings)
Canonical: https://scaleengineer.com/dsa/problems/number-of-wonderful-substrings
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Hash Table, String
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
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 <= 105`
* `word` consists of lowercase English letters from `'a'` to `'j'`.

# Approaches
## Brute Force with Frequency Map
This approach involves generating every possible substring of the input `word` and then checking each one to see if it qualifies as a 'wonderful' string. A string is wonderful if at most one of its characters appears an odd number of times. While straightforward, this method is computationally expensive.
**Time:** O(n^2 * k), where n is the length of the string and k is the number of distinct characters (10). We have two nested loops to generate O(n^2) substrings. Inside the inner loop, we check the frequency array of size k. Since k is constant, the complexity is effectively O(n^2). · **Space:** O(k), where k is the number of distinct characters (10). This is because we only need a small, constant-size array to store character frequencies for each substring. Thus, the space complexity is O(1).
**Pros:** Simple to understand and implement.; Directly follows the problem definition without complex data structures or algorithms.
**Cons:** Highly inefficient due to its `O(n^2)` time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for large inputs as specified in the problem constraints.
### Explanation
We use two nested loops to define all substrings. The outer loop sets the starting index `i`, and the inner loop sets the ending index `j`. For each substring starting at `i`, we maintain a frequency map (an array of size 10 for characters 'a' through 'j'). As we extend the substring by incrementing `j`, we update the character counts. After each character is added, we scan the frequency map to count how many characters have appeared an odd number of times. If this count is 0 or 1, we've found a wonderful substring and increment our total counter.

```java
class Solution {
    public long wonderfulSubstrings(String word) {
        long count = 0;
        int n = word.length();
        for (int i = 0; i < n; i++) {
            int[] freq = new int[10];
            for (int j = i; j < n; j++) {
                freq[word.charAt(j) - 'a']++;
                int oddCount = 0;
                for (int k = 0; k < 10; k++) {
                    if (freq[k] % 2 != 0) {
                        oddCount++;
                    }
                }
                if (oddCount <= 1) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize `wonderful_count = 0`.
- Iterate `i` from `0` to `word.length() - 1` (start of substring).
  - Initialize a frequency array `freq` of size 10 to all zeros.
  - Iterate `j` from `i` to `word.length() - 1` (end of substring).
    - Update the frequency of `word.charAt(j)` in `freq`.
    - Count the number of characters with odd frequencies in `freq`.
    - If the odd count is less than or equal to 1, increment `wonderful_count`.
- Return `wonderful_count`.

## Prefix Parity Bitmask
This highly efficient approach uses bit manipulation to track the parity of character counts. By representing the parity of the first 10 lowercase letters as a 10-bit integer (a bitmask), we can quickly determine if a substring is wonderful. The problem is solved in a single pass through the string by keeping track of the frequencies of previously seen prefix masks.
**Time:** O(n * k), where n is the length of the string and k is the number of distinct characters (10). We iterate through the string once. Inside the loop, we perform a constant number of operations (a few lookups and one update to the frequency array, plus a small loop of size k). Since k is a small constant, the overall time complexity is linear, O(n). · **Space:** O(2^k), where k is the number of distinct characters (10). The frequency array `freq` has a size of 2^10 = 1024. Since this size is constant and does not depend on the input string length `n`, the space complexity is O(1).
**Pros:** Extremely efficient with linear time complexity.; Uses constant space, as the size of the frequency map depends only on the fixed alphabet size.; Scales well for large inputs.
**Cons:** The logic can be less intuitive than a brute-force approach, requiring an understanding of bit manipulation and prefix sums/XORs.
### Explanation
The core idea is that the parity of character counts in a substring `word[j...i]` can be calculated from the parity of prefixes `word[0...i]` and `word[0...j-1]`. We use a bitmask where the `k`-th bit is 1 if the character `'a' + k` has an odd count, and 0 otherwise. The mask for a substring is the XOR sum of the prefix masks of its start and end points (`prefix_mask[i] ^ prefix_mask[j-1]`).

A substring is wonderful if its mask has at most one bit set (i.e., the mask is 0 or a power of 2). We iterate through the string, maintaining the `current_mask` for the prefix ending at the current position. For each position, we count how many previous prefixes, when XORed with `current_mask`, result in a wonderful mask. We use a frequency map (an array of size 1024) to store how many times each prefix mask has been seen. This allows us to find the number of valid starting points for substrings ending at the current position in constant time.

```java
class Solution {
    public long wonderfulSubstrings(String word) {
        long count = 0;
        int mask = 0;
        // freq[mask] stores the number of times a prefix mask has occurred.
        // Size 1024 for 2^10 possible masks.
        long[] freq = new long[1024];
        
        // Base case: an empty prefix has a mask of 0 and occurs once.
        freq[0] = 1;
        
        for (char c : word.toCharArray()) {
            // Update the mask with the current character's parity.
            mask ^= (1 << (c - 'a'));
            
            // Case 1: The substring has all characters with even counts.
            // This occurs if a previous prefix has the same mask as the current one.
            count += freq[mask];
            
            // Case 2: The substring has exactly one character with an odd count.
            // We check for previous prefix masks that differ by one bit.
            for (int i = 0; i < 10; i++) {
                int checkMask = mask ^ (1 << i);
                count += freq[checkMask];
            }
            
            // Increment the frequency of the current mask.
            freq[mask]++;
        }
        
        return count;
    }
}
```
### Algorithm
- Initialize `wonderful_count = 0L`.
- Initialize a bitmask `mask = 0`.
- Initialize a frequency array `freq` of size 1024 to all zeros. This array will store counts of prefix masks.
- Set `freq[0] = 1` to represent the initial empty prefix.
- Iterate through each character `c` of `word`:
  - Update the mask by XORing with the bit corresponding to the character: `mask ^= (1 << (c - 'a'))`.
  - Check for substrings where all character counts are even. The number of such substrings ending at the current position is `freq[mask]`. Add this to `wonderful_count`.
  - Check for substrings where one character count is odd. For each possible character `j` from 'a' to 'j', calculate `check_mask = mask ^ (1 << j)`. The number of such substrings is `freq[check_mask]`. Add this to `wonderful_count`.
  - Increment the frequency of the current prefix mask: `freq[mask]++`.
- Return `wonderful_count`.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
/** * @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;
  };

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```