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.

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;
    }
}

All Problems

All Solutions