这个算法是如何实现滑动window的？

Question

我目前正在准备技术面试，并正在 Python 练习一些数据结构和算法问题。有一个常见问题要求您找到字符串中最长的子字符串，使得该子字符串不包含重复字符。直觉上，我理解如何使用滑动 window 来解决这个问题，这可以通过类似的方式来完成：

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) 时间的非常长的输入字符串，此解决方案效率不高。我找到了另一种滑动 window 实现：

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

在线性时间内解决了问题。我已经分离了代码的作用并理解了各个部分，但无法将其与滑动 window 的工作方式联系起来，这使我无法将这种方法应用于不同的问题。我可以只记住代码，但我想了解第二个代码块中发生的事情与第一个代码块中发生的事情有何相似之处。谁能以简单明了的方式解释这一点，说明第二个变体如何实现滑动 window?

Answer 1

我不会将第一个代码称为“sliding-window 算法”。它似乎只是一种尝试所有可能子串的暴力算法。它可能需要与 n³ 成比例的时间，因为要检查 n² 个子字符串，并且应用 contains_repeats 可能需要与 worst-case 中每个子字符串的 n 成比例的时间。或者更确切地说，如果 k 是字母表中不同字符的数量，那么 contains_repeats 所花费的时间可能与 min(n, k) 成正比；因此第一个算法可能需要时间 n² min(n, k).

第二种算法是sliding-window算法。 window 从索引 start_idx 到索引 i。花费的时间与 n 成正比，因为这两个指标中的每一个都只能增加，不能减少，所以总迭代次数最多为 2n。该算法没有尝试所有可能的子字符串，而是使用 varying-size“window”从左向右“滑动”（永远不会返回）。

请注意，“sliding-window 算法”是一个至少具有两个不同含义的术语。除了这种字符串算法外，有时也用来指代使用卷积的算法。

这个算法是如何实现滑动window的？

How does this algorithm implement a sliding window?

python

algorithm

sliding-window