LeetCode 1915: Number of Wonderful Substrings Solution

Master LeetCode problem 1915 (Number of Wonderful Substrings), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1915. Number of Wonderful Substrings

Medium

Hash Table String Bit Manipulation Prefix Sum

Problem Explanation

Explanation

To solve this problem, we can use a bitmask to represent the parity of each character in the given string. We will iterate through the string and keep track of the prefix XOR value for each character. If a substring has at most one character appearing an odd number of times, then the XOR value of the characters in that substring will have at most one bit set to 1.

For each character in the string, we can toggle the bit representing the parity of that character in the prefix XOR value. We can then count the number of substrings where the XOR value has at most one bit set to 1. To do this, we can use a hashmap to store the count of each prefix XOR value seen so far.

As we iterate through the string, we update the count of substrings based on the previously seen prefix XOR values. Finally, we return the total count of wonderful substrings.

Time complexity: O(N), where N is the length of the input string. Space complexity: O(1) since the size of the hashmap is fixed at 1024 (representing all possible bitmasks for the characters 'a' to 'j').

Solution Code

class Solution {
    public long wonderfulSubstrings(String word) {
        long res = 0;
        int mask = 0;
        long[] count = new long[1024];
        count[0] = 1;
        
        for (char c : word.toCharArray()) {
            mask ^= 1 << (c - 'a');
            res += count[mask];
            
            for (int i = 0; i < 10; i++) {
                res += count[mask ^ (1 << i)];
            }
            
            count[mask]++;
        }
        
        return res;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1915 (Number of Wonderful Substrings)?

This page provides optimized solutions for LeetCode problem 1915 (Number of Wonderful Substrings) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1915 (Number of Wonderful Substrings)?

The time complexity for LeetCode 1915 (Number of Wonderful Substrings) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1915 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1915 in Java, C++, or Python.

Back to LeetCode Solutions