让我们定义以下位集:
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):
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:
B[c,-1] = 0
map = new hash/tree map (bitset->int)
for i from 0 to len(s):
B = NextBitset(B, s[i])
map[B] = i
for each c in alphabet:
B[c,-1] = 0
max_distance = 0
for i from 0 to len(s):
B = NextBitset(B, s[i])
j = map.find(B)
max_distance = max(max_distance, j-i)
a-z
字符可能出现(实际上我也突然想到这一点,可能会有帮助)。 - Elimination