Question

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 1

class Solution:
  def wonderfulSubstrings(self, word: str) -> int:
    cnt = Counter({0: 1})
    ans = st = 0
    for c in word:
      st ^= 1 << (ord(c) - ord("a"))
      ans += cnt[st]
      for i in range(10):
        ans += cnt[st ^ (1 << i)]
      cnt[st] += 1
    return ans

class Solution {
  public long wonderfulSubstrings(String word) {
    int[] cnt = new int[1 << 10];
    cnt[0] = 1;
    long ans = 0;
    int st = 0;
    for (char c : word.toCharArray()) {
      st ^= 1 << (c - 'a');
      ans += cnt[st];
      for (int i = 0; i < 10; ++i) {
        ans += cnt[st ^ (1 << i)];
      }
      ++cnt[st];
    }
    return ans;
  }
}

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

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

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

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