Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1915.html

1915. Number of Wonderful Substrings

Level

Medium

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

Solution

Use bit manipulation. The number of occurrences of each letter can be represented as a bit such that 1 represents an odd number of times and 0 represents an even number of times. For ten letters, the value can be represented with ten bits, in range [0, 1023]. Loop over word and for each index, get the value at the index and update the map, which stores each value’s number of occurrences (here “values” means “keys” of the map). Then loop over all pairs in the map such that the two keys have at most 1 bit that is different, and calculate the number of wonderful substrings.

• Java
• Python
• C++
• Go
• Javascript
• TypeScript

• class Solution {
      public long wonderfulSubstrings(String word) {
          long wonderful = 0;
          final int TOTAL = 1 << 10;
          long[] map = new long[TOTAL];
          map[0] = 1L;
          int value = 0;
          int length = word.length();
          for (int i = 0; i < length; i++) {
              char c = word.charAt(i);
              int index = c - 'a';
              value ^= (1 << index);
              map[value]++;
          }
          for (int i = 0; i < TOTAL; i++) {
              wonderful += map[i] * (map[i] - 1) / 2;
              for (int j = 1; j <= i; j <<= 1) {
                  if ((i & j) == j)
                      wonderful += map[i] * map[i - j];
              }
          }
          return wonderful;
      }
  }
  
  ############
  
  class Solution {
      public long wonderfulSubstrings(String word) {
          int[] counter = new int[1 << 10];
          counter[0] = 1;
          int state = 0;
          long ans = 0;
          for (char c : word.toCharArray()) {
              state ^= (1 << (c - 'a'));
              ans += counter[state];
              for (int i = 0; i < 10; ++i) {
                  ans += counter[state ^ (1 << i)];
              }
              ++counter[state];
          }
          return ans;
      }
  }
  

• class Solution:
      def wonderfulSubstrings(self, word: str) -> int:
          counter = Counter({0: 1})
          state = 0
          ans = 0
          for c in word:
              state ^= 1 << (ord(c) - ord('a'))
              ans += counter[state]
              for i in range(10):
                  ans += counter[state ^ (1 << i)]
              counter[state] += 1
          return ans
  
  ############
  
  # 1915. Number of Wonderful Substrings
  # https://leetcode.com/problems/number-of-wonderful-substrings
  
  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
  
  

• class Solution {
  public:
      long long wonderfulSubstrings(string word) {
          vector<int> counter(1024);
          counter[0] = 1;
          long long ans = 0;
          int state = 0;
          for (char c : word) {
              state ^= (1 << (c - 'a'));
              ans += counter[state];
              for (int i = 0; i < 10; ++i) ans += counter[state ^ (1 << i)];
              ++counter[state];
          }
          return ans;
      }
  };
  

• func wonderfulSubstrings(word string) int64 {
  	counter := make([]int, 1024)
  	counter[0] = 1
  	state := 0
  	var ans int64
  	for _, c := range word {
  		state ^= (1 << (c - 'a'))
  		ans += int64(counter[state])
  		for i := 0; i < 10; i++ {
  			ans += int64(counter[state^(1<<i)])
  		}
  		counter[state]++
  	}
  	return ans
  }
  

• /**
   * @param {string} word
   * @return {number}
   */
  var wonderfulSubstrings = function (word) {
      let counter = new Array(1 << 10).fill(0);
      counter[0] = 1;
      let state = 0;
      let ans = 0;
      for (let c of word) {
          state ^= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
          ans += counter[state];
          for (let i = 0; i < 10; ++i) {
              ans += counter[state ^ (1 << i)];
          }
          ++counter[state];
      }
      return ans;
  };
  
  

• function wonderfulSubstrings(word: string): number {
      const cnt: number[] = new Array(1 << 10).fill(0);
      cnt[0] = 1;
      let ans = 0;
      let st = 0;
      for (const c of word) {
          st ^= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
          ans += cnt[st];
          for (let i = 0; i < 10; ++i) {
              ans += cnt[st ^ (1 << i)];
          }
          cnt[st]++;
      }
      return ans;
  }
  
  

All Problems

All Solutions