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

Question

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

algorithmcomputer-science

11

假设我们有一个字符串s。我们想要找到s的最长子串的长度，使得子串中的每个字符都出现偶数次（可以是零）。时间复杂度：O(nlgn)，空间复杂度：O(n)。

首先，很明显子串的长度必须是偶数。其次，我熟悉滑动窗口方法，其中我们固定右侧索引right，并寻找最左侧的索引以匹配您的条件。我试图在这里应用这个想法，但无法真正构思出来。

此外，对我来说似乎优先队列可能会派上用场（因为O(nlogn)的要求有点暗示了它）

我很高兴能得到帮助！

- Elimination

当您说“子字符串”时，您是指连续的子字符串，还是可以省略字符（例如子序列）？ - tobias_k

是的，一个连续的子字符串（而不是子序列） - Elimination

1

没错，另一个问题会非常简单。仍然想要澄清一下。 - tobias_k

字母表大小被认为是固定的吗？ - amit

@amit，是的，为了简单起见，我们甚至可以假设只有a-z字符可能出现（实际上我也突然想到这一点，可能会有帮助）。 - Elimination

@Elimination 我认为在这种情况下可以在O(n)时间内完成...让我构思一个解决方案，看看它是否可行。 - amit

2个回答

4

我不确定amit具体提出的是什么，如果这是他的想法，请将其视为另一种解释。这可以在单次遍历中完成。

为字符串的每个索引生成一个与字母表长度相等的位集。在遍历字符串时存储每个唯一位集的第一个索引。更新当前和先前看到的位集之间的最大间隔。

例如，对于字符串"aabccab":

  a a b c c a b
  0 1 2 3 4 5 6 (index)

                _
0 1 0 0 0 0 1 1  |  (vertical)
0 0 0 1 1 1 1 0  |  bitset for
0 0 0 0 1 0 0 0 _|  each index
  ^           ^
  |___________|

   largest interval
   between current and
   previously seen bitset

每次迭代的更新可以通过预处理每个字符的位掩码来实现O(1)，以与前一个位集进行XOR操作：

bitset     mask
  0         1     1
  1   XOR   0  =  1
  0         0     0

意思是更新与字母表位集中第一个位相关联的字符。

- גלעד ברקן

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

让我们定义以下位集：

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)