我在一个网站上发现了以下问题。
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 a , b , a(last character) , aba.
我试着解决它。我实现了一个O(n^2)的解决方案(n是输入字符串的长度)。但是期望的时间复杂度是O(n)。我不能在0 (n)内解出它。我找到了下面的解决方案，但我不明白。你能不能帮我理解一下下面这个问题的O(n)解决方案或者想出一个O(n)的解决方案?我的O(N^2)方法-对于每个子字符串检查它是否最多有一个奇数计数字符。使用10个字符的数组可以在O(1)时间内完成此检查。
class Solution {
public:
long long wonderfulSubstrings(string str) {
long long ans=0;
int idx=0; long long xorsum=0;
unordered_map<long long,long long>mp;
mp[xorsum]++;
while(idx<str.length()){
xorsum=xorsum^(1<<(str[idx]-'a'));
// if xor is repeating it means it is having even ouccrences of all elements
// after the previos ouccerence of xor.
if(mp.find(xorsum)!=mp.end())
ans+=mp[xorsum];
mp[xorsum]++;
// if xor will have at most 1 odd character than check by xoring with (a to j)
// check correspondingly in the map
for(int i=0;i<10;i++){
long long temp=xorsum;
temp=temp^(1<<i);
if(mp.find(temp)!=mp.end())
ans+=mp[temp];
}
idx++;
}
return ans;
}
};
代码中有两个主要的算法技巧，位掩码和前缀和，如果你以前从未见过它们，可能会感到困惑。让我们先看看如何从概念上解决这个问题。
对于字符串S的任何子字符串，我们想要计算10个可能的字母中的每一个出现的次数，并询问每个数字是偶数还是奇数。
例如，对于子字符串s = accjjc，我们可以将其总结为:奇数# a，偶数# b，奇数# c，偶数# d，偶数# e，偶数# f，偶数# g，偶数# h，偶数# i，偶数# j。这有点长，所以我们可以使用位掩码来总结它。:对于每个字母a-j，如果计数为奇数，则输入1，如果计数为偶数，则输入0。这将为我们提供一个10位二进制字符串，在我们的示例中为1010000000。
可以将其视为普通整数(或long - long，取决于整数的表示方式)。当我们看到另一个字符时，计数是偶数还是奇数。在位掩码上，这与翻转单个位或异或操作相同。如果我们再添加一个'a'，我们可以通过将其与数字1000000000XORing来更新位掩码，使其以'偶数# a'开头。
我们要计算最多有一个字符计数为奇数的子字符串的个数。这与计算位掩码最多有一个1的子字符串的数量相同。有11个这样的位掩码:10 - 0字符串，每个字符串对应10个可能的位置中的每一个都有一个1。如果将其解释为整数，则后十个字符串是2的前十个幂:1<<0, 1<<1, 1<<2, ... 1<<9。
现在，我们想要计算O(n)时间内所有子字符串的位掩码。首先，解决一个更简单的问题:计算所有前缀的位掩码，并将这些计数存储在hashmap中。我们可以通过从一开始就保持一个正在运行的位掩码，并对该字母xorsum=xorsum^(1<<(str[idx]-'a'))对应的位执行异或更新来实现这一点。这显然可以在单个O(n)时间传递字符串中完成。
我们如何得到任意子字符串的计数?答案是前缀和:任何子字符串中的字母计数都可以用两个前缀计数中的任意一个来表示。例如，对于s = accjjc，假设我们想要对应于子字符串'jj'的位掩码。此子字符串可以写成两个前缀之差:'jj' = 'accjj' - 'acc'.
以同样的方式，我们要减去两个前缀字符串的计数。然而，我们只有位掩码告诉我们每个字母的频率是偶数还是奇数。在位掩码的运算中，我们对每个位置取模2，因此坐标相减变成异或。
这意味着counts(jj) = counts(accjj) - counts(acc)变成bitmask(jj) = bitmask(accjj) ^ bitmask(acc).
仍然有一个问题:我描述的算法仍然是二次的。如果，在每个前缀处，我们遍历所有之前的前缀位掩码，并检查我们的掩码是否异或旧掩码是11个目标位掩码之一，我们仍然有一个二次元运行时间。相反，您可以使用异或是其自身逆的事实:如果a ^ b = c，则b = a ^ c。所以，不是使用旧的前缀掩码进行异或，而是使用11个目标掩码进行异或，并添加我们看到该掩码的次数:ans+=mp[xorsum]计算以当前索引结尾的子字符串，其位掩码为xorsum ^ 0000000000 = xorsum。之后的循环对位掩码为十个目标位掩码之一的子字符串进行计数。最后，你只需要添加当前的前缀掩码来更新计数:mp[xorsum]++。