我目前正在为技术面试做准备,并使用Python练习一些数据结构和算法问题。有一个常见的问题要求你找到一个字符串中最长的子串,使得该子串不包含重复字符。直观地,我知道如何使用滑动窗口来解决这个问题,可以像这样做:
def longest_substring(s: str) -> int:
longest_sub_string = 0
if len(s) == 1:
return 1
for window_size in range(len(s) + 1, 0, -1):
for i in range(len(s) - window_size + 1):
window = s[i:i+window_size]
if not self.contains_repeats(window) and len(window) > longest_sub_string:
longest_sub_string = len(window)
return longest_sub_string
def contains_repeats(s: str = None) -> bool:
splt = list(s)
if len(list(set(splt))) < len(splt):
return True
然而,这种解决方案对于非常长的输入字符串不是很高效,需要花费类似于O(n^2)的时间。我找到了一种替代的滑动窗口实现:
def longest_substring(s: str) -> int:
last_idxs = {}
max_len = 0
start_idx = 0
for i in range(0, len(s)):
if s[i] in last_idxs:
start_idx = max(start_idx, last_idxs[s[i]] + 1)
max_len = max(max_len, i-start_idx + 1)
last_idxs[s[i]] = i
return max_len
这个算法可以在线性时间内解决问题。我已经分析了代码并理解了各个部分,但是无法将其与滑动窗口的工作方式联系起来,这阻止了我能够将此方法应用于不同的问题。我可以仅仅记住这段代码,但我希望能够理解第二个代码块中发生的事情与第一个代码块中发生的事情类似的原因。有人可以简单地解释一下吗,以展示第二种变体如何实现滑动窗口?
'aabbbcccccccccccccccccgdef'
返回 5。 - wwii