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'.To solve #1915 Number of Wonderful Substrings, the key observation is that a substring is considered wonderful if at most one character appears an odd number of times. Since the string only contains the first ten lowercase letters, we can efficiently track parity using bit manipulation.
Maintain a bitmask representing the parity (even or odd count) of each character seen so far. Each bit in the mask corresponds to one character. As you iterate through the string, update the mask and use a hash table to store how often each mask has appeared as a prefix.
A substring is wonderful if the current mask matches a previously seen mask (all counts even) or differs by exactly one bit (only one character has an odd count). By checking these possibilities and accumulating counts, we can efficiently count valid substrings.
This approach leverages prefix parity states and limits the mask size to 10 bits, making the algorithm very efficient with linear traversal of the string.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bitmask + Prefix Frequency Hashing | O(n * 10) | O(2^10) |
Happy Coding
Use these hints if you're stuck. Try solving on your own first.
For each prefix of the string, check which characters are of even frequency and which are not and represent it by a bitmask.
Find the other prefixes whose masks differs from the current prefix mask by at most one bit.
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.
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.
1import java.util.HashMap;
2
3public class WonderfulSubstrings {
4 public static int wonderfulSubstrings(String word) {
5
The Java solution utilizes a HashMap for prefix status, allowing dynamic and fast lookup of prefix statuses. The toggling and counting strategy remains consistent with C and C++.
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.
Time Complexity: O(n^3),
Space Complexity: O(1).
1def is_wonderful(substr):
2 freq = [0] * 10
3
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems involving prefix sums, bitmasking, and substring counting are common in technical interviews at companies like FAANG. This problem tests optimization, bit manipulation, and efficient counting techniques.
The optimal approach uses a bitmask combined with prefix frequency counting. Each prefix maintains a 10-bit mask representing parity of character counts, and we count matching masks or masks differing by one bit to identify valid wonderful substrings.
Bit manipulation efficiently tracks whether each character count is even or odd. Since the problem only involves the first ten lowercase letters, a 10-bit mask can represent all parity states, enabling constant-time checks for valid substrings.
A hash table or frequency array is commonly used to store how many times each prefix bitmask has appeared. This allows quick lookup of previously seen states while scanning the string.
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.