Is Number of Wonderful Substrings easy or hard?

The problem is rated Medium on LeetCode. The challenge comes from recognizing that substring validity depends only on odd/even parity and encoding that state using a bitmask. Once the parity insight is clear, the prefix counting solution becomes straightforward.

Number of Wonderful Substrings Python/Java solution

Most implementations maintain an integer mask and an array of size 1024 storing prefix counts. For every character, toggle its bit, add matches for the same mask, then check the 10 masks with one bit flipped. The same logic works across Python, Java, C++, C#, and JavaScript.

How to solve Number of Wonderful Substrings in O(n)?

Maintain a 10-bit mask representing odd/even counts of characters 'a' through 'j'. As you scan the string, update the mask using XOR. Count how many previous prefixes have the same mask (all characters even) and masks differing by exactly one bit (one odd character). Store prefix frequencies in an array of size 1024.

What is the best approach for Number of Wonderful Substrings?

The optimal approach uses a bitmask with prefix frequency counting. Each character toggles one of 10 bits representing odd/even frequency. A hash table or array tracks how many times each mask appeared, allowing you to count substrings where the parity mask differs by zero or one bit. This runs in O(n) time.

Is Number of Wonderful Substrings asked at Google/Amazon/Meta?

Parity-mask string problems similar to this appear in interviews at companies like Google and Amazon. The technique of encoding character parity with bitmasks and combining it with prefix frequency counting is a common interview pattern.

What data structure is used in Number of Wonderful Substrings?

The core data structure is a frequency map (often an array of size 1024) that stores how many times each bitmask has appeared. The algorithm also uses bit manipulation to represent character parity and a prefix-sum style traversal of the string.

What is the time complexity of Number of Wonderful Substrings?

The optimal solution runs in O(n * 10) time, which simplifies to O(n). For each character you check the current mask and the 10 masks formed by flipping one bit. Space complexity is O(2^10) because there are only 1024 possible parity states.

Description Hints 2 Solution Video 38:20

1915. Number of Wonderful Substrings

Medium66.8% acceptance2 companies

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

Constraints:

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

Asked at 2 companies

Uber

Google

Topics

Hints open one at a time

Hint 1

For each prefix of the string, check which characters are of even frequency and which are not and represent it by a bitmask.

Hint 2

Find the other prefixes whose masks differs from the current prefix mask by at most one bit.

38:20

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:

2 def wonderfulSubstrings(self, word: str) -> int:

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"aba"

Input

"aabb"

Input

"he"

Your code is saved on this device.Solution