【LeetCode周赛247】C LeetCode 1915. 最美子字符串的数目

摘要：
将奇偶性的状态压缩成一个二进制数字。

题目

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

例如，$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 <= 10^5$
$word$ 由从 $a$ 到 $j$ 的小写英文字母组成

前缀和

根据题意，在某个最美子串中，所有的字母出现的的次数要么全为偶数次，要么有一位字母出现了奇数次。
很容易想到使用前缀和快速拿到出现次数。配合暴力枚举子串，复杂度为 $n \times (n + 1) / 2$，必然超时。

定义前缀和数组 $presum[N][j]$，其中 $1 <= N <= 10^5$, $j = 10$. $presum[i][j]$ 表示在原字符串中从第 $1$ 位开始到第 $i$ 位结尾的子串某个字母出现的次数。

那么一段下标为 $[a, b]$ 的子串，它的某个字母 $j$ 出现次数可表示为 $presum[b][j] - presum[a - 1][j]$。根据数学知识，如果它是一个奇数，那么 $presum[b][j]$ 和 $presum[a - 1][j]$ 奇偶性不同，反之相同。

那么问题就变成了：在字符串所有子串中，每个字母对应的 $presum[b][j]$ 和 $presum[a - 1][j]$ 奇偶性不同的情况最多只能出现一次的子串一共多少。

现在对前缀和数组的某一项的每一位字母出现的奇偶性状态进行压缩。
对于某个子串，我们可以将出现奇数次的字母记为 $1$，将出现偶数次的字母记为 $0$.由于字母范围为字母表前 $10$ 个，那么一段子串的每一位字母出现次数的奇偶性状态可表示为一个 $10$ 位的二进制数。

$presum[b][j]$ 和 $presum[a - 1][j]$ 的各字母出现奇偶性的状态都可以表示成一个 $10$ 位二进制数。
对于以下标 $b$ 结尾的前缀子串的奇偶性状态，以下标 $a$ 结尾的子串共有 $11$ 种对应的状态可以满足奇偶性不同的情况最多一次的条件。其中，完全和该状态相同的状态表示奇偶性不同的情况出现 $0$ 次，即奇偶性完全相同；另外 $10$ 种对应着原状态的 $10$ 位奇偶状态的某一位不同。
比如一个状态为：0001000110. 满足条件的 $11$ 种状态如下：
0001000110
1001000110
0101000110
0011000110
0000000110
0001100110
0001010110
0001001110
0001000010
0001000100
0001000111
那么我们考虑遍历字符串，当遍历到第 $b$ 位时，枚举上述 $11$ 种状态，如果之前出现过其中一种或多种，那么以那一种或多种对应下标开始到 $b$ 结束的子串即满足要求。

所以我们需要一个计数数组，将从第 $1$ 个字符开始到遍历到的每一位字符结束的状态数量记录下来供后面使用。
考虑到二进制状态数字最高 $10$ 位，所以可以开一个数量为 $10000000000_2$（$1024_{10}$）的计数数组.

另外，思考一下计数数组的第 $0$ 位初始化为什么应该是 $1$.
在字符串第 $0$ 位之前，存在一个状态 0000000000，它表示每一位字母出现了 $0$ 次（均为偶数）。所以这种状态在遍历之前计数为 $1$.

举例：对于一个字符串 $a$ 来说，它的最美子串数目为 $1$. 我们初始化状态 0000000000 的数量为 $1$，这样，在遍历到字符串第 $0$ 个数的时候状态为 1000000000，$11$ 个期望的状态中共有一种符合与之构成最美子串的状态，即初始化的 0000000000. 这两个状态有一位字母的出现的奇偶性不同。对应子串为 $a$.

class Solution {
public:
    static constexpr int N = 1024;
    int cnt[N];    
    long long res;
    long long wonderfulSubstrings(string word) {
        int len = word.size();
        vector<vector<int>> presum(len + 1, vector<int> (10, 0));
        memset(cnt, 0, sizeof cnt);
        cnt[0]++;
        for (int i = 0; i < len; i++) {
            char c = word[i];
            for (int j = 0; j < 10; j++) {
                presum[i + 1][j] = presum[i][j];
            }
            presum[i + 1][c - 'a']++;
            /*
            for (int j = 0; j < 10; j++) {
                cout << presum[i + 1][j] << ' ';
            }
            cout << endl;
            */
            int state = 0;
            for (int j = 0; j < 10; j++)
                state = state * 2 + presum[i + 1][j] % 2;    // 跟10进制一样的。一段十进制序列转换成十进制数：for (int j = 0; j < len; j++) res = res * 10 + seq[j];
            // 对于当前以i结尾的字符串，根据当前状态枚举每一种可能的状态，通过cnt数组查看之前有没有出现过
            // 首先是完全一样的状态，如果在[0, i - 1]这一段出现过跟以i结尾的字符串完全一致的状态，那么它们构成的子串有0个字母出现了奇数次
            res += cnt[state];
            // 其次是10种不同状态，每种有一位和当前状态不同
            for (int j = 0; j < 10; j++) {
                res += cnt[state ^ (1 << j)];
            }
            cnt[state]++;
        }
        return res;
    }
};

代码涉及到的两个额外知识，且都和位运算有关:

将一段二进制序列转换成十进制数：
对于以下标b结束的前缀和字母计数序列，需要将它的各位奇偶性状态压缩成一个二进制数。代码是：
1
2
3
int state = 0;
for (int j = 0; j < 10; j++)
state = state * 2 + presum[i + 1][j] % 2;
一个二进制数 $x$，它的距离最低位 $k$ 个数字不同且其他位相同的二进制数为：
x ^ (1 << k)

原题链接： LeetCode 1915. 最美子字符串的数目