代码之家 › 专栏 › 技术社区 › Elimination

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

computer-science algorithm

Elimination · 技术社区 · 7 年前

假设我们有一根绳子 s . 我们想找出 S 这样子字符串中的每个字符出现偶数次(可能为零)。
厕所时间: O(nlgn) 。厕所空间: O(n)

首先,很明显子字符串的长度必须是偶数。第二,我熟悉滑动窗口法,我们在这里锚定一些 right 索引并查找最左边的索引以匹配您的条件。我试着在这里应用这个想法,但并没有真正形成它。

而且,在我看来,优先级队列可以派上用场(因为 O(NLGN) 需求有点暗示它)

我很乐意帮忙!

2 回复 | 直到 7 年前

amit 7 年前

让我们定义以下位集:

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 )

注意条件:

对于子字符串为true s[i,j] 如果且仅当索引的位集 我 与索引的位集相同 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)

×××¢× ××¨×§× 7 年前

我不知道阿米特到底是怎么建议的,所以如果是这样,请考虑另一种解释。这可以在一次遍历中完成。

例如,字符串“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

表示更新与字母表位集中第一位相关联的字符。