1915. Number of Wonderful Substrings

MediumBit ManipulationHash TableStringPrefix Sum
Leetcode Link

Problem Description

The problem presents a concept of a 'wonderful' string which is defined as a string where at most one letter appears an odd number of times. We are tasked with counting the number of wonderful non-empty substrings within a given string word. This string word contains only the first ten lowercase English letters ('a' through 'j'). It is important to note that we must consider each occurrence of a wonderful substring separately even if it appears multiple times in word. A substring is defined as a contiguous sequence of characters within a string.

Intuition

The intuition behind solving this problem lies in recognizing patterns and efficiently tracking the frequency of characters as we consider different substrings. A naive approach would be to check all possible substrings and count how many meet the criteria, but this would be too slow for larger strings.

The solution uses bitwise operations to keep track of the frequency of each letter in a space-efficient manner. We can represent the frequency of each of the 10 letters by a single bit in an integer (st). If a letter appears an even number of times, its corresponding bit is set to 0, and if it appears an odd number of times, its bit is set to 1. The wonderful property is then satisfied if at most one bit is set to 1 in this integer.

We initialize a counter to keep track of the occurrences of each bit pattern as we iterate through word. As we consider each new character, we update our bit pattern state st. For each new character, we add to our answer the count of the current state st to capture the same pattern we have already seen (which automatically represents an even number of each letter in the substring). Additionally, we iterate through each bit position to flip it, checking if there is a pattern that had all bits even except for the current one. This would represent substrings with all even counts of characters except one, meeting the 'wonderful' criteria.

The Counter structure is used to keep track of how many times we've encountered each bit pattern. This allows us to quickly calculate the new number of wonderful substrings each time we process a new character in the string. By adding the counter for the current state and the counter for states with one bit flipped, we can account for all the substrings that end at the current character and are wonderful.

Using this method, we efficiently compute the number of wonderful substrings in the given word without checking every possible substring individually.

Learn more about Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is a good use case for backtracking?

Solution Approach

The solution implemented in the reference code uses a combination of bit manipulation, hashing (via a Counter dictionary), and comprehension of the property of wonderful substrings.

  1. Bit Manipulation: To track the odd or even frequency of each letter without storing the counts individually, the solution uses bit manipulation, where each bit in a state integer st represents the count of a particular letter from 'a' to 'j'. The least significant bit corresponds to a, the second least significant bit to b, and so on up to the tenth bit for j. If a letter has appeared an odd number of times, the corresponding bit is set to 1, and if it has appeared an even number of times, it's set to 0.

  2. Counter Dictionary: This is used to hash the number of times each bit pattern appeared. It's implemented using Python's Counter class.

  3. State Transition: When a new character from the string word is processed, we calculate the new state st by using the XOR operation st ^= 1 << (ord(c) - ord("a")). The XOR operation with 1 shifted left by (ord(c) - ord("a")) positions flips the bit corresponding to the new character. This changes the bit from 0 to 1 if the character count was even (representing an odd count now) and from 1 to 0 if the count was odd (representing an even count now).

  4. Counting Wonderful Substrings: The number of wonderful substrings that can be formed ending with the current character is the sum of:

    • The number of times the current state st has been seen before, which is ans += cnt[st], because if we've seen this pattern before, it means there is a substring ending here that maintains the evenness of all previously processed characters.
    • The number of times each bit-flipped state has occurred, which is computed with ans += cnt[st ^ (1 << i)] for i in range(10). Flipping each bit simulates having all the other letters appear an even number of times and only one letter an odd number of times, which is still a 'wonderful' state.

  5. Updating the Counter: After accounting for the new wonderful substrings, cnt[st] += 1 updates the count for the current state.

The solution goes through each character only once, and for each character, it checks 10 possible states—those with no letters appearing an odd number of times and those with exactly one. This results in a linear O(n*10) solution, where n is the length of word.

In terms of space complexity, the counter keeps track of at most 2^10 (1024) different bit patterns, which corresponds to a bitwise representation of letter counts. So the space complexity is O(2^k) where k is the number of unique letters, which is 10 in this case. However, it only keeps track of bit patterns that have been seen, so the actual space used could be much less.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Example Walkthrough

Let's consider the string word = "aba". We will walk through the solution approach step by step.

  1. Bit Manipulation: We are using bit manipulation to track the frequency of each letter using the state integer st. Initially, st = 0, which means all bits are set to 0, indicating even counts of all letters.

  2. Counter Dictionary: We initialize a Counter with cnt = {0:1}, which implies we have already encountered a state with all even counts once (an empty substring).

  3. State Transition:

    • Process the first character 'a': The state transition is st ^= 1 << (ord('a') - ord('a')), hence st = 0b0000000001. The Counter now recognizes one odd appearance of 'a'.

    • Process the second character 'b': The state changes with st ^= 1 << (ord('b') - ord('a')), so st becomes 0b0000000010. Now we have both 'a' and 'b' with odd appearances (but not in the same substring).

  4. Counting Wonderful Substrings:

    • For st = 0b0000000001 after processing the first 'a':

      • ans += cnt[st] (the previous same state), so ans = 0+1 = 1 because an all-even state was seen before, and the current state is the wonderful substring "a".
      • Flip each bit in st and add those counts: There are no previous 1-bit-flipped states, so no addition here.

    • Considering the state 0b0000000010 after processing 'b':

      • ans += cnt[st] (the previous same state), so ans = 1+0 = 1 because there's yet no state with only 'b' with an odd count.
      • Flipping each bit of st (checking for 0b0000000001 and 0b0000000010), we find ans += cnt[0b0000000001] = 1, hence ans = 2. This represents the wonderful substring "b".

    • Now, process the third character, another 'a':

      • Update st using st ^= 1 << (ord('a') - ord('a')), st is now 0b0000000010 again.
      • ans += cnt[st] would result in ans = 2+1 = 3 because we have seen this state before, representing the substrings "b" and "aba".
      • By flipping each bit in st and adding those counts, we find ans += cnt[0b0000000001] = 1; therefore, ans = 4. This represents the substring "ab".

  5. Updating the Counter: After each character is processed, we update the counter for the current state:

    • After the first 'a', cnt[0b0000000001] = 1 as we've seen the state of 'a' once.
    • After 'b', cnt[0b0000000010] = 1 as we've seen the state of 'b' once.
    • After the second 'a', cnt[0b0000000010] = 2 since we've returned to this state.

In the end, ans = 4. We have the wonderful substrings: "a", "b", "ab", "aba". Each of these substrings meets the criteria of at most one letter having an odd count within the substring.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def wonderfulSubstrings(self, word: str) -> int:
5        # Initialize a counter for the mask state, starting with the 0 state seen once
6        mask_count = Counter({0: 1})
7      
8        # Initialize answer and mask state
9        wonderful_count = 0
10        current_mask = 0
11      
12        # Iterate over the characters in the word
13        for char in word:
14            # Toggle the bit for the current character in the mask state
15            current_mask ^= 1 << (ord(char) - ord('a'))
16          
17            # Add to the wonderful string count the number of times this mask state has been seen
18            # This covers the case where the substring has an even count of all characters
19            wonderful_count += mask_count[current_mask]
20          
21            # Check all masks that differ by one bit, which correspond to having
22            # exactly one character with an odd count
23            for i in range(10):
24                # Toggle the i-th bit to check for a previous state that would
25                # complement the current state to make a wonderful substring
26                wonderful_count += mask_count[current_mask ^ (1 << i)]
27          
28            # Increment the count for the current mask state
29            mask_count[current_mask] += 1
30      
31        # Return the total count of wonderful substrings
32        return wonderful_count
33
1class Solution {
2    /**
3     * Returns the number of 'wonderful' substrings in a given word.
4     * A 'wonderful' substring is defined as a substring that has at most one character appear
5     * an odd number of times.
6     *
7     * @param word The input string for which we want to find the number of 'wonderful' substrings.
8     * @return The count of 'wonderful' substrings.
9     */
10    public long wonderfulSubstrings(String word) {
11        // Initialize an array to count the state occurrences.
12        int[] stateCount = new int[1 << 10]; // 1 << 10 because there are 10 possible characters (a-j).
13        stateCount[0] = 1; // Empty string is a valid starting state.
14        long totalCount = 0; // This will hold the total number of 'wonderful' substrings.
15        int state = 0; // This represents the bitmask state of characters a-j. Each bit represents if a character has an odd or even count.
16
17        // Loop over each character in the string
18        for (char c : word.toCharArray()) {
19            // Toggle the bit corresponding to the character c.
20            state ^= 1 << (c - 'a');
21          
22            // Add the count of the current state to answer.
23            totalCount += stateCount[state];
24          
25            // Try toggling each bit to account for at most one character that can appear an odd number of times.
26            for (int i = 0; i < 10; ++i) {
27                totalCount += stateCount[state ^ (1 << i)];
28            }
29          
30            // Increment the count of the current state.
31            ++stateCount[state];
32        }
33
34        // The total number of wonderful substrings is now calculated in totalCount.
35        return totalCount;
36    }
37}
38
1class Solution {
2public:
3    long long wonderfulSubstrings(string word) {
4        // Array to count the number of times each bit mask appears
5        int count[1024] = {1}; // Initialize with 1 at index 0 to handle the empty substring scenario
6        long long totalSubstrings = 0; // Total count of wonderful substrings
7        int state = 0; // Current state of bit mask representing character frequency parity
8      
9        // Iterate over each character in the string
10        for (char ch : word) {
11            // Update the state: Flip the bit corresponding to the current character
12            state ^= 1 << (ch - 'a');
13          
14            // Add the count of the current state to the total substrings count
15            totalSubstrings += count[state];
16          
17            // Check for states that differ by exactly one bit from the current state
18            for (int i = 0; i < 10; ++i) {
19                totalSubstrings += count[state ^ (1 << i)];
20            }
21          
22            // Increment the count for the current state
23            ++count[state];
24        }
25      
26        // Return the total count of wonderful substrings
27        return totalSubstrings;
28    }
29};
30
1function wonderfulSubstrings(word: string): number {
2    const count: number[] = new Array(1 << 10).fill(0); // An array to store the count of all character state occurrences
3    count[0] = 1; // Initial state with 0 odd characters
4    let totalWonderfulSubstrings = 0; // Variable to count the number of wonderful substrings
5    let charState = 0; // Bitmask state representing the parity of character counts
6
7    // Iterate through each character of the word
8    for (const char of word) {
9        // XOR the current state with the bit representing the current character's position
10        charState ^= 1 << (char.charCodeAt(0) - 'a'.charCodeAt(0));
11
12        // Add the count of the current state to the total count of wonderful substrings
13        totalWonderfulSubstrings += count[charState];
14
15        // Check every possible character state with one bit flipped
16        for (let i = 0; i < 10; ++i) {
17            totalWonderfulSubstrings += count[charState ^ (1 << i)];
18        }
19
20        // Increment the count of the current character state
21        count[charState]++;
22    }
23
24    // Return the total number of wonderful substrings
25    return totalWonderfulSubstrings;
26}
27
Not Sure What to Study? Take the 2-min Quiz：

What's the relationship between a tree and a graph?

Time and Space Complexity

Time Complexity:

Analyzing the code, the main part contributing to time complexity is the two nested loops: the outer loop iterating over each character of the string once, and the inner loop iterating 10 times for each character (since an alphabet in lowercase has 26 letters).

  • The outer loop runs n times where n is the length of the input string word.
  • The inner loop runs up to 10 times for each iteration of the outer loop, irrespective of the input string.

Thus, the overall time complexity can be computed as O(10n) or O(n) when we ignore the constant factor.

The operations within the loops (bitwise XOR, dictionary access/update) are constant time.

Hence, the time complexity of the code is: O(n).

Space Complexity:

For space complexity, the code maintains a counter cnt dictionary that at most contains the number of different states that a bitset of size 10 (size corresponding to the first 10 alphabets) can have, plus 1 for the initial {0:1} state. The st variable holds the current state and changes in-place.

The states are bitsets that correspond to the parity (even or odd count) of each letter, and there can be 2^10 such states.

So, the space complexity is determined by the number of different states that can be held in counter cnt, which gives us 2^10.

Therefore, the space complexity of the code is: O(2^10) or O(1) because 2^10 is a constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer techniques do you use to check if a string is a palindrome?

Recommended Readings

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫