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

Question

假设我们有一个字符串s.我们希望找到最长子串的长度,使得子串中的s每个字符都出现偶数次(可能为零).
WC时间:O(nlgn).WC空间: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）也是恒定的。

注意条件：

子字符串中的每个字符出现偶数次

对于子串来说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)