Question

1915. 最美子字符串的数目

English Version

题目描述

如果某个字符串中 至多一个 字母出现 奇数 次，则称其为 最美 字符串。

• 例如，"ccjjc" 和 "abab" 都是最美字符串，但 "ab" 不是。

给你一个字符串 word ，该字符串由前十个小写英文字母组成（'a' 到 'j'）。请你返回 word 中 最美非空子字符串 的数目_。_如果同样的子字符串在_ _word 中出现多次，那么应当对 每次出现 分别计数_。_

子字符串 是字符串中的一个连续字符序列。

 

示例 1：

输入：word = "aba"
输出：4
解释：4 个最美子字符串如下所示：
- "aba" -> "a"
- "aba" -> "b"
- "aba" -> "a"
- "aba" -> "aba"

示例 2：

输入：word = "aabb"
输出：9
解释：9 个最美子字符串如下所示：
- "aabb" -> "a"
- "aabb" -> "aa"
- "aabb" -> "aab"
- "aabb" -> "aabb"
- "aabb" -> "a"
- "aabb" -> "abb"
- "aabb" -> "b"
- "aabb" -> "bb"
- "aabb" -> "b"

示例 3：

输入：word = "he"
输出：2
解释：2 个最美子字符串如下所示：
- "he" -> "h"
- "he" -> "e"

 

提示：

• 1 <= word.length <= 105
• word 由从 'a' 到 'j' 的小写英文字母组成

解法

方法一：前缀异或 + 计数

由于字符串中只包含 $10$ 个小写字母，因此可以用一个长度为 $10$ 的二进制数表示字符串中每个字母的奇偶性，其中第 $i$ 位为 $1$ 表示第 $i$ 个字母出现了奇数次，为 $0$ 表示第 $i$ 个字母出现了偶数次。

我们遍历字符串的每个字符，用一个变量 $st$ 维护当前字符串的前缀异或值，用一个数组 $cnt$ 维护每个前缀异或值出现的次数，初始时 $st = 0$, $cnt[0] = 1$。

对于当前遍历到的字符，我们更新其前缀异或值。如果当前的前缀异或值出现了 $cnt[st]$ 次，也就意味着有 $cnt[st]$ 个子字符串满足所有字母的出现次数均为偶数，因此我们将答案增加 $cnt[st]$。此外，对于 $0 \le i < 10$，如果当前的前缀异或值 $st$ 的第 $i$ 位为 $1$，那么我们还可以找到一个字母出现了奇数次，我们将答案增加 $cnt[st \oplus (1 << i)]$。最后，我们将 $st$ 出现的次数增加 $1$。继续遍历下一个字符，直到遍历完整个字符串。

时间复杂度 $O(n \times \Sigma)$，空间复杂度 $O(2^{\Sigma})$，其中 $\Sigma = 10$，而 $n$ 为字符串的长度。

相似题目：

• 1371. 每个元音包含偶数次的最长子字符串

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