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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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:

1
2
3
4
5

Input: word = "he"
Output: 2
Explanation: The two wonderful substrings are underlined below:
- "**h**e" -> "h"
- "h**e**" -> "e"

Solution

Method 1 - Using Bitmasks

To solve this problem, we will use a technique based on bitmasks to track the odd/even occurrences of each character.

Approach

  1. Bitmask Representation:

    • We use a bitmask of length 10 (as the problem limits the characters from ‘a’ to ‘j’, hence 10 characters).
    • Each bit in the bitmask will represent if the corresponding character (‘a’ to ‘j’) has occurred an even (bit 0) or odd (bit 1) number of times up to the current position in the string.

  2. Prefix Signature:

    • We use a prefix signature to track the occurrences of the characters up to the current index.
    • Initialize prefix map with {0: 1} to account for single character substrings and to handle cases where the bitmask does not change.

  3. Count Substrings:

    • Traverse the string and update the bitmask for each character.
    • Check how many previous states of the bitmask (from the prefix map) can form a valid wonderful substring. This includes the current bitmask being exactly the same as a previous one or differs by a single bit (to allow one odd character).

  4. Valid Masks:

    • We check if the current bitmask matches any of the previous occurrences.
    • We also check by toggling each bit to allow at most one character to have an odd count.

Code

 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

 class Solution {
     public long wonderfulSubstrings(String word) {
         long ans = 0;
         HashMap<Integer, Integer> prefix = new HashMap<>();
         int currentMask = 0;
         prefix.put(0, 1);
 
         for (char ch : word.toCharArray()) {
             currentMask ^= 1 << (ch - 'a');
 
             if (prefix.containsKey(currentMask)) {
                 ans += prefix.get(currentMask);
             }
 
             for (int i = 0; i < 10; i++) {
                 int targetMask = currentMask ^ (1 << i);
                 ans += prefix.getOrDefault(targetMask, 0);
             }
             
             prefix.put(currentMask, prefix.getOrDefault(currentMask, 0) + 1);
         }
         
         return ans;
     }
 }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        ans: int = 0
        prefix: defaultdict[int, int] = defaultdict(int)
        current_mask: int = 0
        prefix[0] = 1
        
        for ch in word:
            current_mask ^= 1 << (ord(ch) - ord('a'))
            
            ans += prefix[current_mask]

            for i in range(10):
                ans += prefix[current_mask ^ (1 << i)]
            
            prefix[current_mask] += 1
        
        return ans

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string, as we traverse the string once and perform constant-time operations for each character.
  • 🧺 Space complexity: O(n) as we may store up to n unique prefix bitmasks in the hashmap.