#1915

Medium

LeetCode Problem Workspace

Number of Wonderful Substrings

Count the number of wonderful non-empty substrings of a given string based on frequency conditions of characters.

hash table string bit manipulation prefix sum

Problem Statement

A wonderful string is one where at most one character appears an odd number of times. Given a string consisting of the first ten lowercase English letters, return the number of wonderful non-empty substrings in the string. Each occurrence of the same substring should be counted separately.

A substring is a contiguous sequence of characters in the string. For example, in the string 'aba', substrings like 'a', 'ab', 'ba', and 'aba' are considered. Your goal is to find the number of such substrings that qualify as wonderful based on the aforementioned condition.

Examples

Example 1

Input: word = "aba"

Output: 4

The four wonderful substrings are underlined below:

"aba" -> "a"
"aba" -> "b"
"aba" -> "a"
"aba" -> "aba"

Example 2

Input: word = "aabb"

Output: 9

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

The two wonderful substrings are underlined below:

"he" -> "h"
"he" -> "e"

Constraints

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

Solution Approach

Using a Bitmask Representation

Each character in the string is mapped to a bit in an integer. The bitmask represents the characters with odd frequencies. For each prefix of the string, check which characters have even or odd frequencies, and use the bitmask to track the frequency state. This reduces the complexity compared to checking all possible substrings directly.

Tracking Frequencies with Hash Table

Use a hash table to track the occurrences of bitmasks. The idea is to count how often each bitmask has occurred during the traversal of the string. This allows the identification of substrings that meet the criteria for being wonderful efficiently.

Iterating Over Prefixes

Iterate over all prefixes of the string, calculating the bitmask for each prefix. For each new prefix, check if the current bitmask matches the previous ones or differs by just one bit, which would indicate the substring is wonderful. This approach ensures the solution is efficient and handles the constraints well.

Complexity Analysis

Metric	Value
Time	O(NA)
Space	O(N)

The time complexity is O(N), where N is the length of the string, due to the single pass required to process each character and update the bitmask. The space complexity is O(N) for storing the frequency of each bitmask in the hash table, which can grow with the number of unique bitmask states.

What Interviewers Usually Probe

Candidate can apply bit manipulation to represent frequencies efficiently.
Candidate identifies the need for a hash table to track frequency states over prefixes.
Candidate recognizes the importance of reducing the problem complexity with prefix-based analysis.

Common Pitfalls or Variants

Common pitfalls

Failing to efficiently represent frequencies with a bitmask, leading to unnecessary complexity.
Not considering the need to track multiple occurrences of bitmask states using a hash table.
Overcomplicating the solution by checking all substrings individually instead of focusing on prefixes.

Follow-up variants

Handling a larger set of characters beyond 'a' to 'j'.
Optimizing the algorithm to handle even larger strings with stricter time limits.
Exploring dynamic programming approaches to optimize the bitmask handling.

FAQ

What is the optimal approach to solve the 'Number of Wonderful Substrings' problem?

The optimal solution uses a bitmask to represent the frequency of characters in the string and a hash table to track the number of times each bitmask has appeared.

How do you represent character frequencies for this problem?

Character frequencies are represented as a bitmask, where each bit corresponds to whether a character has appeared an odd or even number of times.

What is a wonderful substring in the context of this problem?

A wonderful substring is one where at most one character has an odd frequency of appearance.

What data structures are most useful for solving this problem?

Hash tables for tracking bitmask frequencies and bit manipulation for efficient frequency state representation are key data structures for this problem.

How can GhostInterview help with bitmask and hash table problems?

GhostInterview provides focused practice on problems involving bitmasking and hash tables, offering strategies for handling complex string and frequency-based challenges.

terminal

Solution

Solution 1

#### Python3

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

Continue Practicing

#1930 unique length 3 palindromic subsequences #1371 find the longest substring containing vowels in even counts #1177 can make palindrome from substring