Skip to content

1915. Number of Wonderful Substrings

Difficulty Topics

Description

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.

Given a string word that consists of the first ten lowercase English letters ('a' through 'j'), return the number of wonderful non-empty substrings in word. If the same substring appears multiple times in word, then count each occurrence separately.

A substring is a contiguous sequence of characters in a string.

 

Example 1:

Input: word = "aba"
Output: 4
Explanation: The four wonderful substrings are underlined below:
- "aba" -> "a"
- "aba" -> "b"
- "aba" -> "a"
- "aba" -> "aba"

Example 2:

Input: word = "aabb"
Output: 9
Explanation: The nine wonderful substrings are underlined below:
- "aabb" -> "a"
- "aabb" -> "aa"
- "aabb" -> "aab"
- "aabb" -> "aabb"
- "aabb" -> "a"
- "aabb" -> "abb"
- "aabb" -> "b"
- "aabb" -> "bb"
- "aabb" -> "b"

Example 3:

Input: word = "he"
Output: 2
Explanation: The two wonderful substrings are underlined below:
- "he" -> "h"
- "he" -> "e"

 

Constraints:

  • 1 <= word.length <= 105
  • word consists of lowercase English letters from 'a' to 'j'.

Solution

number-of-wonderful-substrings.py
class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        count = [1] + [0] * 1023
        curr = res = 0

        for x in word:
            curr ^= (1 << ord(x) - ord('a'))
            res += count[curr]

            for bit in range(10):
                delta = 1 << bit
                res += count[curr ^ delta]

            count[curr] += 1

        return res