Number of Wonderful Substrings
MedPrompt
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 <= 105wordconsists of lowercase English letters from'a'to'j'.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves generating every possible substring of the input word and then checking each one to see if it qualifies as a 'wonderful' string. A string is wonderful if at most one of its characters appears an odd number of times. While straightforward, this method is computationally expensive.
Algorithm
- Initialize
wonderful_count = 0. - Iterate
ifrom0toword.length() - 1(start of substring).- Initialize a frequency array
freqof size 10 to all zeros. - Iterate
jfromitoword.length() - 1(end of substring).- Update the frequency of
word.charAt(j)infreq. - Count the number of characters with odd frequencies in
freq. - If the odd count is less than or equal to 1, increment
wonderful_count.
- Update the frequency of
- Initialize a frequency array
- Return
wonderful_count.
Walkthrough
We use two nested loops to define all substrings. The outer loop sets the starting index i, and the inner loop sets the ending index j. For each substring starting at i, we maintain a frequency map (an array of size 10 for characters 'a' through 'j'). As we extend the substring by incrementing j, we update the character counts. After each character is added, we scan the frequency map to count how many characters have appeared an odd number of times. If this count is 0 or 1, we've found a wonderful substring and increment our total counter.
class Solution { public long wonderfulSubstrings(String word) { long count = 0; int n = word.length(); for (int i = 0; i < n; i++) { int[] freq = new int[10]; for (int j = i; j < n; j++) { freq[word.charAt(j) - 'a']++; int oddCount = 0; for (int k = 0; k < 10; k++) { if (freq[k] % 2 != 0) { oddCount++; } } if (oddCount <= 1) { count++; } } } return count; }}Complexity
Time
O(n^2 * k), where n is the length of the string and k is the number of distinct characters (10). We have two nested loops to generate O(n^2) substrings. Inside the inner loop, we check the frequency array of size k. Since k is constant, the complexity is effectively O(n^2).
Space
O(k), where k is the number of distinct characters (10). This is because we only need a small, constant-size array to store character frequencies for each substring. Thus, the space complexity is O(1).
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem definition without complex data structures or algorithms.
Cons
Highly inefficient due to its
O(n^2)time complexity.Will result in a 'Time Limit Exceeded' (TLE) error for large inputs as specified in the problem constraints.
This highly efficient approach uses bit manipulation to track the parity of character counts. By representing the parity of the first 10 lowercase letters as a 10-bit integer (a bitmask), we can quickly determine if a substring is wonderful. The problem is solved in a single pass through the string by keeping track of the frequencies of previously seen prefix masks.
Algorithm
- Initialize
wonderful_count = 0L. - Initialize a bitmask
mask = 0. - Initialize a frequency array
freqof size 1024 to all zeros. This array will store counts of prefix masks. - Set
freq[0] = 1to represent the initial empty prefix. - Iterate through each character
cofword:- Update the mask by XORing with the bit corresponding to the character:
mask ^= (1 << (c - 'a')). - Check for substrings where all character counts are even. The number of such substrings ending at the current position is
freq[mask]. Add this towonderful_count. - Check for substrings where one character count is odd. For each possible character
jfrom 'a' to 'j', calculatecheck_mask = mask ^ (1 << j). The number of such substrings isfreq[check_mask]. Add this towonderful_count. - Increment the frequency of the current prefix mask:
freq[mask]++.
- Update the mask by XORing with the bit corresponding to the character:
- Return
wonderful_count.
Walkthrough
The core idea is that the parity of character counts in a substring word[j...i] can be calculated from the parity of prefixes word[0...i] and word[0...j-1]. We use a bitmask where the k-th bit is 1 if the character 'a' + k has an odd count, and 0 otherwise. The mask for a substring is the XOR sum of the prefix masks of its start and end points (prefix_mask[i] ^ prefix_mask[j-1]).
A substring is wonderful if its mask has at most one bit set (i.e., the mask is 0 or a power of 2). We iterate through the string, maintaining the current_mask for the prefix ending at the current position. For each position, we count how many previous prefixes, when XORed with current_mask, result in a wonderful mask. We use a frequency map (an array of size 1024) to store how many times each prefix mask has been seen. This allows us to find the number of valid starting points for substrings ending at the current position in constant time.
class Solution { public long wonderfulSubstrings(String word) { long count = 0; int mask = 0; // freq[mask] stores the number of times a prefix mask has occurred. // Size 1024 for 2^10 possible masks. long[] freq = new long[1024]; // Base case: an empty prefix has a mask of 0 and occurs once. freq[0] = 1; for (char c : word.toCharArray()) { // Update the mask with the current character's parity. mask ^= (1 << (c - 'a')); // Case 1: The substring has all characters with even counts. // This occurs if a previous prefix has the same mask as the current one. count += freq[mask]; // Case 2: The substring has exactly one character with an odd count. // We check for previous prefix masks that differ by one bit. for (int i = 0; i < 10; i++) { int checkMask = mask ^ (1 << i); count += freq[checkMask]; } // Increment the frequency of the current mask. freq[mask]++; } return count; }}Complexity
Time
O(n * k), where n is the length of the string and k is the number of distinct characters (10). We iterate through the string once. Inside the loop, we perform a constant number of operations (a few lookups and one update to the frequency array, plus a small loop of size k). Since k is a small constant, the overall time complexity is linear, O(n).
Space
O(2^k), where k is the number of distinct characters (10). The frequency array `freq` has a size of 2^10 = 1024. Since this size is constant and does not depend on the input string length `n`, the space complexity is O(1).
Trade-offs
Pros
Extremely efficient with linear time complexity.
Uses constant space, as the size of the frequency map depends only on the fixed alphabet size.
Scales well for large inputs.
Cons
The logic can be less intuitive than a brute-force approach, requiring an understanding of bit manipulation and prefix sums/XORs.
Solutions
Solution
class Solution {public long wonderfulSubstrings(String word) { int[] cnt = new int[1 << 10]; cnt[0] = 1; long ans = 0; int st = 0; for (char c : word.toCharArray()) { st ^= 1 << (c - 'a'); ans += cnt[st]; for (int i = 0; i < 10; ++i) { ans += cnt[st ^ (1 << i)]; } ++cnt[st]; } return ans; }}/** * @param {string} word * @return {number} */ var wonderfulSubstrings = function (word) { const cnt = new Array(1024).fill(0); cnt[0] = 1; let ans = 0; let st = 0; for (const c of word) { st ^= 1 << (c.charCodeAt() - " a ".charCodeAt()); ans += cnt[st]; for (let i = 0; i < 10; ++i) { ans += cnt[st ^ (1 << i)]; } cnt[st]++; } return ans; };class Solution {public: long long wonderfulSubstrings(string word) { int cnt[1024] = {1}; long long ans = 0; int st = 0; for (char c : word) { st ^= 1 << (c - 'a'); ans += cnt[st]; for (int i = 0; i < 10; ++i) { ans += cnt[st ^ (1 << i)]; } ++cnt[st]; } return ans; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.