Number of Wonderful Substrings Leetcode Solution

by

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 <= 105
  • 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

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Related :

Related :

Leave a Comment