algorithm - 每个字符出现偶数次(可能为零)的最长子串

Question

Suppose we have a string s. We want to find the length of the longest substring of s such that every character in the substring appears even number of times (possible zero).
WC Time: O(nlgn). WC space: O(n)

首先，很明显子字符串必须是偶数长度。其次，我熟悉滑动窗口方法，我们在其中锚定一些 right 索引并寻找最左边的索引来匹配您的标准。我试图在这里应用这个想法，但无法真正表达它。

此外，在我看来，优先级队列可能会派上用场(因为 O(nlgn) 要求有点暗示)

我很乐意提供帮助!

Answer 1

让我们定义以下位集:

B[c,i] = 1 if character c appeared in s[0,...,i] even number of times.

计算 B[c,i] 需要线性时间(对于所有值):

for all c:
  B[c,-1] = 0
for i from 0 to len(arr):
  B[c, i] = B[s[i], i-1] XOR 1

由于字母表的大小不变，位集也是如此(对于每个 i)。

注意条件:

every character in the substring appears even number of times

对于子字符串 s[i,j] 为真当且仅当索引 i 的位集与索引 j 的位集相同时> (否则，该子串中有重复奇数次的位；反之:如果有重复次数的位，则其位不能相同)。

因此，如果我们将所有位集存储在某个集合(哈希集/树集)中，并且只保留最新条目，则此预处理需要 O(n) 或 O(nlogn) 时间(取决于散列/树集)。

在第二次迭代中，对于每个索引，找到具有相同位集的较远索引(O(1)/O(logn)，取决于哈希/树集)，找到子字符串长度，并将其标记为候选。最后，选择最长的候选人。

此解决方案的位集空间为 O(n)，时间为 O(n)/O(nlogn)，具体取决于是否使用哈希/树解决方案。

---

伪代码:

def NextBitset(B, c): # O(1) time
  for each x in alphabet \ {c}:
    B[x, i] = B[x, i-1]
   B[c, i] = B[c, i-1] XOR 1

for each c in alphabet: # O(1) time
  B[c,-1] = 0
map = new hash/tree map (bitset->int)

# first pass: # O(n)/O(nlogn) time
for i from 0 to len(s):
   # Note, we override with the latest element.
   B = NextBitset(B, s[i])
   map[B] = i

for each c in alphabet: # O(1) time
  B[c,-1] = 0
max_distance = 0
# second pass: O(n)/ O(nlogn) time.
for i from 0 to len(s):
  B = NextBitset(B, s[i])
  j = map.find(B)  # O(1) / O(logn)
  max_distance = max(max_distance, j-i)