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'.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.
C++
Java
Python
C#
JavaScript
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.
Time Complexity: O(n^3),
Space Complexity: O(1).
| 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), |
LeetCode 1915. Number of Wonderful Substrings • Happy Coding • 12,410 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