Page Contents

Number of Wonderful Substrings

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 <= 10⁵
word consists of lowercase English letters from 'a' to 'j'.

Program:

class Solution:
    # idea: we don't need to know exact substring to define if it's "wonderful" or not
    #   but rather if number of occurrences of each letter is odd/even;
    #   so there are only two states for each letter, so we can use binary mask to represent any substring
    #
    #   for example "0101" means represend ("d" even number, "c" - odd, "b" - even, "a" - odd);
    #
    #   we can iterate through word and remember all prefix masks
    #   + for each new mask find number of previous prefix masks that make substring in between "wonderful"
    #
    #   if (current_mask ^ earlier_mask) == mask_with_0_or_1_bit_set => we have a "wonderful" substring
    #
    #   example: "ccbbc"
    #       "" - { mask: 000, mask_count: [0, 0, 0, 0, 0, 0, 0, 1] }
    #       "c" - { mask: 100, mask_count: [0, 0, 0, 1, 0, 0, 0, 1] }
    #       "cc" - { mask: 000, mask_count: [0, 0, 0, 1, 0, 0, 0, 2] }
    #       "ccb" - { mask: 010, mask_count: [0, 0, 0, 1, 0, 1, 0, 2] }
    #       "ccbb" - { mask: 000, mask_count: [0, 0, 0, 1, 0, 1, 0, 3] }
    #       "ccbbc" - { mask: 100, mask_count: [0, 0, 0, 2, 0, 1, 0, 3] }
	#
	#        what is mask count:
	#                mask: [111, 110, 101, 100, 011, 010, 001, 000]
	#        mask_count:   [  0,   0,   0,   2,   0,   1,   0,   3]
	#        we saw 2 "100" masks, 1 "010" mask and 3 "000" masks
    
    def wonderfulSubstrings(self, word: str) -> int:
        mask = 0
        mask_count = [0] * 1024
        mask_count[mask] += 1
        res = 0

        for letter in word:
            mask ^= 1 << ord(letter) - ord("a")
            res += mask_count[mask]
            for i in range(10):
                res += mask_count[mask ^ 1 << i]
            mask_count[mask] += 1
        return res

Credit : Here

Weekly Contest 247

Biweekly Contest 55

Number of Wonderful Substrings Leetcode Solution