Number of Wonderful Substrings

Problem Statement

In this problem, we are introduced to the concept of a wonderful string. A string is considered wonderful if at most one character in the string appears an odd number of times. For example, the strings "ccjjc" and "abab" both qualify as wonderful because either no letter or exactly one letter appears an odd number of times in them.

Given a specific string word composed solely of the first ten lowercase English letters (from 'a' to 'j'), our task is to determine how many non-empty substrings of word are wonderful. It is important to note that if identical substrings occur multiple times in word, each occurrence is counted separately.

A substring is defined as a contiguous sequence of characters within a string. This problem requires assessing each possible substring of word and counting how many of those satisfy the wonderful condition.

Examples

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:
- "**h**e" -> "h"

• "he" -> "e"

Constraints

• 1 <= word.length <= 105
• word consists of lowercase English letters from 'a' to 'j'.

Approach and Intuition

To solve this problem, let's break down the challenge using the provided examples:

1. For each substring, we need to verify if it can be considered wonderful. This involves counting the frequency of each character and checking if at most only one character has an odd count.

2. To efficiently explore all possible substrings of word, understanding the constraints is crucial:

   • word length is up to 105, suggesting that a naive approach, which might require examining all substrings, could be too slow. Specifically, as there are potentially over 5,000,000 substrings, naive frequency counting for each could be inefficient.

3. An insightful approach involves using bitwise operations:

   • Keep a frequency mask, where each bit represents the odd/even status of character counts from 'a' to 'j'. This bitwise representation (odd-even status mask) helps in quickly understanding how the addition of a character affects the wonderful property of a substring.
   • Iterate over the string and update this mask as you expand substrings. Use this mask to check if the substring formed by extending to the current character maintains a wonderful state (only one or zero bits set).

4. Using hash tables or arrays to store intermediate results, such as the number of times each mask appears, can significantly cut down redundant calculations, enabling us to compute results faster.

By following this technique, every substring's wonderful nature is evaluated indirectly through the update of the mask, making the process much quicker and computationally feasible even for large strings. Each step essentially adjusts or checks the bit corresponding to a character in linear time relative to the string length with constant extra space relative to the character set size, leading to efficient overall performance.

Solutions

class Solution {
    public long countWonderfulSubstrings(String text) {
        int length = text.length();
    
        Map<Integer, Integer> countMap = new HashMap<>();
        countMap.put(0, 1);
    
        int currentMask = 0;
        long totalCount = 0L;
        for (int j = 0; j < length; j++) {
            char ch = text.charAt(j);
            int bitIndex = ch - 'a';
    
            currentMask ^= (1 << bitIndex);
                
            totalCount += countMap.getOrDefault(currentMask, 0);
            countMap.put(currentMask, countMap.getOrDefault(currentMask, 0) + 1);
    
            for (int b = 0; b < 10; b++) {
                totalCount += countMap.getOrDefault(currentMask ^ (1 << b), 0);
            }
        }
        return totalCount;
    }
}