有一个O（n）。让
S是字符串。刚去通过阵列有两个指针
i和
j并跟踪数
K之间不同的字母
S[i]和
S[j]。增量
j每当这个数小于或等于
n和增量
i每当
K大于
n。还要记住最长的子字符串
K等于
n。
在实现中，您还需要一个哈希表来跟踪字母的最后一次出现。
Python实现：
def longest(S,n): i = j = K = 0 res = (0,0) last = {} while i < len(S): # if current substring is better than others than save if K == n and j - i > res[1] - res[0]: res = (i,j) # if we reach the end of the string, we're done. if j + 1 > len(S): break # if we can go further with the right end than do it elif K <= n and j + 1 <= len(S): if not last.has_key(S[j]): K = K + 1 last[S[j]] = j j = j + 1 # if we must go further with the left end than do it else: if last.has_key(S[i]): del last[S[i]] K = K - 1 i = i + 1 return S[res[0]:res[1]]
