We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Wonderful Substrings

Number: 2044

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, DE Shaw, Google

Problem Description

Given a string made up of the first ten lowercase English letters ('a' to 'j'), count the number of non-empty substrings that are "wonderful". A substring is considered wonderful if at most one character in it appears an odd number of times.

Key Insights

  • Use a bitmask to represent the parity (even/odd occurrence) for each of the ten letters.
  • A prefix-based approach allows us to convert the problem of checking substrings into comparing prefix bitmasks.
  • When the XOR of the bitmask for two prefixes yields 0 (or has only one bit set), it indicates that the corresponding substring is wonderful.
  • Use a hash table (or dictionary) to store and count how many times a particular bitmask has appeared.

Space and Time Complexity

Time Complexity: O(n * 10) ≈ O(n), where n is the length of the input string. Space Complexity: O(2^10) = O(1) since there are at most 1024 distinct bitmask values.

Solution

We utilize a bitmask to monitor the frequency parity of each letter in the given string. As we iterate through the string, we update the bitmask by flipping the bit corresponding to the current letter. A hash table (or dictionary) is maintained to track the number of times each bitmask occurs as a prefix. For the current bitmask:

  • Adding the count of the same bitmask seen before accounts for substrings where all characters have even frequency.
  • Flipping each bit (one at a time) and adding the count from the hash table counts the substrings where exactly one character has an odd frequency. This efficient use of bit manipulation along with prefix sums allows us to check all substrings without explicitly enumerating them.

Code Solutions

# Python solution with line-by-line comments

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        # Dictionary to count how many times each bitmask has been seen
        prefix_mask_count = {0: 1}  # initialize with 0 bitmask seen once (empty prefix)
        current_mask = 0  # current bitmask representing parity of counts
        total_wonderful = 0  # count of wonderful substrings
        
        # Iterate over each character in the word
        for char in word:
            # Determine the bit position for the current character (0 for 'a', 1 for 'b', etc.)
            bit_index = ord(char) - ord('a')
            # Flip the corresponding bit in the current_mask
            current_mask ^= (1 << bit_index)
            
            # Check for substrings where all characters have even counts
            total_wonderful += prefix_mask_count.get(current_mask, 0)
            
            # Check for substrings where exactly one character count is odd
            for i in range(10):
                # Flip one bit at a time to allow one odd character
                candidate_mask = current_mask ^ (1 << i)
                total_wonderful += prefix_mask_count.get(candidate_mask, 0)
            
            # Update the count for the current_mask in the hash table
            prefix_mask_count[current_mask] = prefix_mask_count.get(current_mask, 0) + 1
        
        return total_wonderful
← Back to All Questions