Number of Wonderful Substrings — LeetCode 1915 Python Solution

The problem

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.

Example

Input

word = "aba"

Output

4

Explanation

The four wonderful substrings are underlined below:

Python solution

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        cnt = Counter({0: 1})
        ans = st = 0
        for c in word:
            st ^= 1 << (ord(c) - ord("a"))
            ans += cnt[st]
            for i in range(10):
                ans += cnt[st ^ (1 << i)]
            cnt[st] += 1
        return ans

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 1915. Number of Wonderful Substrings is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems