1915. Number of Wonderful Substrings

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'.

 

Solutions

Solution: Prefix Bit Manipulation + Hash Table

• Time complexity: O(n*10)
• Space complexity: O(2¹⁰)

 

JavaScript

/**
 * @param {string} word
 * @return {number}
 */
const wonderfulSubstrings = function (word) {
  const BASE_CHAR_CODE = 'a'.charCodeAt(0);
  const CHARS = 'abcdefghij'.length;
  const BIT = 2 ** CHARS;
  const counts = Array.from({length: BIT}).fill(0);
  let result = (current = 0);

  counts[0] = 1;

  for (const char of word) {
    current ^= 1 << (char.charCodeAt(0) - BASE_CHAR_CODE);
    result += counts[current];

    for (let index = 0; index < CHARS; index++) {
      result += counts[current ^ (1 << index)];
    }
    counts[current] += 1;
  }
  return result;
};