Number of Wonderful Substrings

#514 Most AskedMedium

Number of Wonderful Substrings #514 Most Asked

Medium

Bloomberg LP

3 views

Topics:

ArraysBit Manipulation

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `word`? Are there any specific character sets I should expect (e.g., only lowercase letters, ASCII characters)?
Could the input string `word` be empty or null?
What is the definition of a 'wonderful' substring in this context? Specifically, what constitutes an odd vs. even occurrence of a digit?
If there are multiple 'wonderful' substrings, should I return the total count of them, or something else?
Are there any constraints on the time or space complexity I should be aware of, given the potential input size?

Brute Force Solution

Approach

We need to find special sections within a larger string. The brute force method looks at every possible section of the string, one by one. For each section, it checks if it's a 'wonderful' substring according to the problem's rules.

Here's how the algorithm would work step-by-step:

Start by considering the very first character of the string as a section all by itself.
Then, consider the first two characters as a section, then the first three, and so on, until you reach the entire string.
Next, start from the second character and repeat the same process: consider it alone, then with the third character, then with the third and fourth characters, and so on.
Keep doing this, each time starting from the next character in the string, until you have looked at every possible section of the string.
For each of these sections, carefully count how many times each different character (like 'a', 'b', 'c', etc.) appears in that section.
Determine if the counts meet the condition to be wonderful, i.e. to have at most one character appearing an odd number of times.
If a section meets the 'wonderful' condition, add it to the list of wonderful substrings.
In the end, count the total number of wonderful substrings you found and report this total count.

Code Implementation

def number_of_wonderful_substrings_brute_force(word):
    number_of_wonderful_substrings = 0
    string_length = len(word)

    for starting_index in range(string_length):
        for ending_index in range(starting_index, string_length):
            substring = word[starting_index : ending_index + 1]
            character_counts = {}

            # Count character frequencies in current substring
            for char in substring:
                character_counts[char] = character_counts.get(char, 0) + 1

            odd_count_characters = 0
            for count in character_counts.values():

                #Check to see if we have too many odd frequency characters
                if count % 2 != 0:
                    odd_count_characters += 1

            if odd_count_characters <= 1:

                # Substring is wonderful, increment counter
                number_of_wonderful_substrings += 1

    return number_of_wonderful_substrings

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates through all possible substrings of the input string s of length n. The outer loop iterates n times, and the inner loop iterates up to n times in the worst case, resulting in n*n combinations. For each substring, the algorithm counts the frequency of each character, which takes O(n) time in the worst case, as it might need to iterate through all the characters of the substring. Thus the total time complexity is approximately n * n * n which simplifies to O(n³).

Space Complexity

O(1) – The provided algorithm iterates through all substrings and counts character frequencies within each substring. While checking if a substring is wonderful involves character counting, this process can be done using a fixed-size array or bitmask (e.g., of size 26 for lowercase English letters) to track character counts, regardless of the string's length. Therefore, the auxiliary space used for character counting remains constant. No other significant data structures are created that scale with the input string's length, N, so the overall space complexity is O(1).

Optimal Solution

Approach

The challenge asks us to count special substrings within a bigger string. The smart way to solve it involves cleverly tracking the counts of characters to quickly identify and count the "wonderful" substrings that meet our conditions, rather than checking every possible substring directly. This avoids unnecessary work and makes the process much faster.

Here's how the algorithm would work step-by-step:

Imagine each character as contributing to a 'state' we are tracking. This state represents how many times each character appears (whether it's an even or odd number of times).
We'll keep a record of how many times we've seen each possible 'state' so far.
As we move through the string, update our 'state' based on the character we encounter. If a character appears, flip the odd/even state.
For each position in the string, check how many previous 'states' are 'wonderful' based on the current state. A substring is considered wonderful if it has at most one character appearing an odd number of times. So we must compare the current state to all other possible states with at most one odd character.
Add the number of "wonderful" states found for each position to a total count.
The final count is the number of wonderful substrings in the whole string.

Code Implementation

def number_of_wonderful_substrings(word):
    number_of_characters = 10
    state_counts = {0: 1}
    current_state = 0
    wonderful_substring_count = 0

    for character in word:
        character_index = ord(character) - ord('a')
        current_state ^= (1 << character_index)

        wonderful_substring_count += state_counts.get(current_state, 0)

        # Check for substrings with one odd count.
        for index in range(number_of_characters):
            mask = 1 << index
            flipped_state = current_state ^ mask
            wonderful_substring_count += state_counts.get(flipped_state, 0)

        # Update the count of current state.
        state_counts[current_state] = state_counts.get(current_state, 0) + 1

    return wonderful_substring_count

Big(O) Analysis

Time Complexity

O(n) – We iterate through the string of length n once. In each iteration, we update a state (represented by a fixed-size bitmask, where each bit represents the parity of a character's count). We then iterate through all possible states with at most one bit flipped, which is a constant 11 operations (10 characters + original state). Therefore, the dominant operation is the single pass through the string, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm uses a fixed-size array or hash map to store the counts of each possible 'state'. Since there are at most 2^10 possible states (as each character can be either even or odd, and there are only 10 distinct characters), the space required to store these counts remains constant, irrespective of the input string's length N. Thus, the auxiliary space used is independent of the input size. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty string input	Return 0, as an empty string has no substrings.
String with length of 1	Check if the single character represents a 'wonderful' substring (i.e., has at most one odd count), and return 1 if so, 0 otherwise.
String with all identical characters	The number of wonderful substrings will depend on the character. If the character is the one represented by the bitmask, the count increases; otherwise, it's 0 or 1.
String with maximum allowed length	Ensure the solution uses a data structure (like a hash map) with efficient lookup and insertion, to prevent time limit exceedance.
String contains characters other than the first 10 lowercase letters	Ensure the bitmask calculation correctly handles such characters, perhaps by ignoring them or raising an exception.
Integer overflow when calculating the count of substrings	Use a 64-bit integer type (long in Java/C++) to store the count to prevent integer overflow.
The prefix frequency count is very high for some masks	Make sure the data structures used to store prefix frequencies can handle a large number of collisions or a high load factor.
No wonderful substrings exist	The algorithm should correctly return 0 in cases where no substring satisfies the 'wonderful' condition.

Empty string input

How to Handle:

Return 0, as an empty string has no substrings.

String with length of 1

How to Handle:

Check if the single character represents a 'wonderful' substring (i.e., has at most one odd count), and return 1 if so, 0 otherwise.

String with all identical characters

How to Handle:

The number of wonderful substrings will depend on the character. If the character is the one represented by the bitmask, the count increases; otherwise, it's 0 or 1.

String with maximum allowed length

How to Handle:

Ensure the solution uses a data structure (like a hash map) with efficient lookup and insertion, to prevent time limit exceedance.

String contains characters other than the first 10 lowercase letters

How to Handle:

Ensure the bitmask calculation correctly handles such characters, perhaps by ignoring them or raising an exception.

Integer overflow when calculating the count of substrings

How to Handle:

Use a 64-bit integer type (long in Java/C++) to store the count to prevent integer overflow.

The prefix frequency count is very high for some masks

How to Handle:

Make sure the data structures used to store prefix frequencies can handle a large number of collisions or a high load factor.

No wonderful substrings exist

How to Handle:

The algorithm should correctly return 0 in cases where no substring satisfies the 'wonderful' condition.