Number of Wonderful Substrings

Medium Arrays & Hashing Prefix Sum Strategy Original on LeetCode

Reported atUber

Number of Wonderful Substrings is a medium arrays & hashing problem solved with the prefix sum strategy pattern. The best approach, optimal (prefix parity masks + counting), runs in O(10 · n) time and O(2^10) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (extend every start) up.

Problem

A string is called wonderful when at most one of its letters appears an odd number of times. For example, "aabbc" is wonderful (only c is odd), while "abc" is not.

You are given word, made only of the first ten lowercase letters 'a' through 'j'. Return how many non-empty substrings of word are wonderful. Substrings at different positions are counted separately, even if they spell the same text.

Examples

Example 1

Input
word = "abab"
Output
7
Why
The four single letters, "aba", "bab" (one odd letter each) and "abab" (no odd letters) qualify; "ab" and "ba" have two odd letters.

Example 2

Input
word = "cdcc"
Output
7
Why
Four single letters plus "cc", "cdc" and "dcc". The whole string has both c (3) and d (1) odd, so it does not count.

Example 3

Input
word = "gh"
Output
2
Why
Only "g" and "h" work; "gh" has two letters with an odd count.

Constraints

  • 1 <= word.length <= 10^5
  • word contains only the letters 'a' to 'j'.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (extend every start)O(n²)O(1)
Optimal (prefix parity masks + counting)O(10 · n)O(2^10)

1Brute force (extend every start)

TimeO(n²)There are n(n + 1) / 2 substrings and each one is checked in O(1) thanks to the running mask.
SpaceO(1)Only the mask and loop indices.

Fix each start index and extend the end one character at a time, flipping that letter's bit in a running parity mask. The substring is wonderful when the mask has at most one bit set.

  1. For each start i, set mask = 0.
  2. For each end j >= i, flip bit word[j] - 'a' in mask.
  3. If mask & (mask - 1) == 0 (zero or one bit set), add 1 to the answer.
class Solution {
    public long wonderfulSubstrings(String word) {
        int n = word.length();
        long count = 0;
        for (int i = 0; i < n; i++) {
            int mask = 0;
            for (int j = i; j < n; j++) {
                mask ^= 1 << (word.charAt(j) - 'a');
                if ((mask & (mask - 1)) == 0) count++;
            }
        }
        return count;
    }
}

2Optimal (prefix parity masks + counting)

TimeO(10 · n)Each character does 11 constant-time lookups.
SpaceO(2^10)A fixed table of 1024 counters, one per possible parity mask.

Let prefix[j] be the parity mask of the first j characters. The substring (i, j] has parity mask prefix[i] ^ prefix[j]. It is wonderful when that XOR is 0 or a single bit, so for every prefix count earlier prefixes with the same mask or a mask that differs in exactly one of the 10 bits. Since there are only 2^10 masks, an array of 1024 counters is enough.

  1. Create freq[1024] and set freq[0] = 1 for the empty prefix.
  2. Walk the string, flipping bit c - 'a' in mask for each character c.
  3. Add freq[mask] (all letters even) and freq[mask ^ (1 << b)] for b in 0..9 (exactly one odd letter).
  4. Then increment freq[mask].
class Solution {
    public long wonderfulSubstrings(String word) {
        long[] freq = new long[1 << 10];
        freq[0] = 1;
        int mask = 0;
        long count = 0;
        for (int k = 0; k < word.length(); k++) {
            mask ^= 1 << (word.charAt(k) - 'a');
            count += freq[mask];
            for (int b = 0; b < 10; b++) {
                count += freq[mask ^ (1 << b)];
            }
            freq[mask]++;
        }
        return count;
    }
}

Edge cases to test

  • A single character: the answer is 1
  • All characters equal: every substring qualifies, n(n + 1) / 2 of them, which needs a 64-bit result
  • Many distinct letters, where most substrings fail
  • Substrings with zero odd letters (even length palindromic counts) must be counted too

Hints

Hint 1

Only the parity (odd or even) of each letter's count matters, and there are just 10 letters. How can you store all 10 parities in one integer?

Hint 2

If the parity mask of the prefix ending at j equals the mask of the prefix ending at i, the substring between them has every count even.

Hint 3

A substring with exactly one odd letter corresponds to two prefix masks that differ in exactly one bit. For each prefix, look up the same mask and the 10 masks one bit away.

FAQ

What is the best time complexity for Number of Wonderful Substrings?

Optimal (prefix parity masks + counting) runs in O(10 · n) time and O(2^10) extra space. Each character does 11 constant-time lookups.

Which pattern does Number of Wonderful Substrings use?

It is a arrays & hashing problem that uses the prefix sum strategy pattern. Other problems with the same pattern: Subarray Sum Equals K, Subarray with given XOR, Range Sum Query - Immutable.

Is there a brute force solution for Number of Wonderful Substrings?

Yes. Brute force (extend every start) takes O(n²) time and O(1) space. Fix each start index and extend the end one character at a time, flipping that letter's bit in a running parity mask.

Which edge cases should I test for Number of Wonderful Substrings?

A single character: the answer is 1; All characters equal: every substring qualifies, n(n + 1) / 2 of them, which needs a 64-bit result; Many distinct letters, where most substrings fail; Substrings with zero odd letters (even length palindromic counts) must be counted too.