Number of Wonderful Substrings - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

MediumHash Table String Bit Manipulation Prefix Sum10 min readAsked at: Uber, Google

Practice this problem

Problem Statement

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'.

Approach Overview

Problem Overview: Given a string consisting of the first ten lowercase letters (a–j), count how many substrings are wonderful. A substring is wonderful when at most one character appears an odd number of times. The task is essentially checking parity of character counts across all substrings efficiently.

Approach 1: Bitmask and Prefix Sum (O(n) time, O(1) space)

The key observation: you only care whether each character count is odd or even. That means you can represent the state of the string using a 10‑bit mask where bit i indicates whether character 'a' + i currently has odd frequency. As you iterate through the string, update this mask using XOR. Each mask represents the parity state of the prefix.

A substring is wonderful if its parity mask has either zero odd characters or exactly one odd character. Using the prefix sum idea, the parity of substring [l..r] equals prefixMask[r] ^ prefixMask[l-1]. To count valid substrings ending at position r, track how many times each mask has appeared using a hash table or array of size 2^10. First add matches where the mask is identical (all even counts). Then flip each of the 10 bits and check those masks to allow exactly one odd character. Each step performs constant work, giving O(n * 10) ≈ O(n) time and O(2^10) space.

This approach relies heavily on bit manipulation. The bitmask compresses parity information into a small integer, making state comparison extremely fast.

Approach 2: Sliding Window (Basic) (O(n^2) time, O(1) space)

A more straightforward idea expands substrings using a sliding window style enumeration. Fix the left boundary and extend the right pointer while tracking frequency counts for the ten characters. After each extension, compute how many characters currently have odd counts. If that number is ≤ 1, the substring is wonderful.

This method uses a small frequency array of size 10 and updates counts as the window expands. Checking the odd-count condition requires scanning the array or maintaining an auxiliary counter. While easy to implement, every starting index may scan many characters, resulting in O(n^2) time in the worst case. Space remains O(1) since the alphabet size is fixed.

Recommended for interviews: The bitmask + prefix frequency approach is what interviewers expect. It reduces the substring parity check to constant-time mask comparisons and demonstrates strong understanding of prefix techniques and parity encoding. The quadratic window approach is useful for reasoning about the problem initially, but the optimized bitmask solution shows the algorithmic insight required for medium-level string problems.

Approach 1: Approach 1: Bitmask and Prefix Sum

This approach uses bitmasking to track the odd/even status of character frequencies. We use a prefix sum technique to maintain these statuses as the string is iterated upon.

The `wonderfulSubstrings` function maintains a `prefixStatus` array where each index represents a binary mask of counts for characters 'a' to 'j'. For each character, we toggles its corresponding bit in `currStatus`. The current status is checked against previous statuses recorded in `prefixStatus` to calculate substrings. Additionally, substrings differing by only one bit (one odd letter) are also counted.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n * k), where n is the length of the string and k is 10 (number of possible characters).
Space Complexity: O(2^k), due to the prefixStatus array for bitmasking.

Try this approach in the editor →

Approach 2: Approach 2: Sliding Window (Basic)

This approach uses a non-optimized sliding window technique over the string to identify all substrings and individually verify their "wonderfulness" by counting character frequencies.

This solution in Python uses a nested loop to generate all possible substrings of the given word. The auxiliary function `is_wonderful` checks each substring to see if at most one character has an odd frequency, defining it as wonderful.

Code

Python

Complexity

Time Complexity: O(n^3),
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Default Approach

Code

Python Java C++Go TypeScript JavaScript

Python

Java

C++

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Approach 1: Bitmask and Prefix Sum	Time Complexity: O(n * k), where n is the length of the string and k is 10 (number of possible characters). Space Complexity: O(2^k), due to the prefixStatus array for bitmasking.
Approach 2: Sliding Window (Basic)	Time Complexity: O(n^3), Space Complexity: O(1).
Default Approach	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Bitmask and Prefix Sum	O(n * 10) ≈ O(n)	O(2^10)	Best general solution. Efficient for large strings and expected in interviews.
Sliding Window (Basic)	O(n^2)	O(1)	Useful for understanding the condition and brute-force reasoning before optimization.

Video Solution

Number of Wonderful Substrings | Clear Intuition | Full Dry Run | Leetcode 1915 | codestorywithMIK • codestorywithMIK • 15,423 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Number of Wonderful Substrings with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Longest Substring Without Repeating Characters

Problem Info

DifficultyMedium

Acceptance66.8%

Approaches3

Reading time10 min

Asked at

Uber Google

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Approach 1: Bitmask and Prefix Sum

Code

Complexity

Approach 2: Approach 2: Sliding Window (Basic)

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents