A wonderful string is a string where at most one letter appears an odd number of times.
"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 <= 105word consists of lowercase English letters from 'a' to 'j'.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.
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.
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.
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.
Python
Time Complexity: O(n^3),
Space Complexity: O(1).
Python
Java
C++
Go
TypeScript
JavaScript
| 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). |
| Approach 2: Sliding Window (Basic) | Time Complexity: O(n^3), |
| Default Approach | — |
| 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. |
Number of Wonderful Substrings | Clear Intuition | Full Dry Run | Leetcode 1915 | codestorywithMIK • codestorywithMIK • 14,628 views views
Watch 9 more video solutions →Practice Number of Wonderful Substrings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor