- 暴力枚举法：枚举所有可能的子串并检查它们是否有重复的字符。时间复杂度为 O(n3)。
- 滑动窗口法：维护一个滑动窗口，该窗口包含的子串没有重复的字符。我们向右移动窗口，并在每个位置更新最长的无重复子串。时间复杂度为O(n)。
代码如下：
def lengthOfLongestSubstring(s: str) -> int: n = len(s) ans = 0 i, j = 0, 0 lookup = set() while i < n and j < n: if s[j] not in lookup: lookup.add(s[j]) j += 1 ans = max(ans, j - i) else: lookup.remove(s[i]) i += 1 return ans
- 哈希表法：使用哈希表来存储每个字符最后出现的位置。然后，我们可以使用两个指针来维护一个窗口。右指针 j 用于扩展当前窗口，而左指针 i 用于排除不在窗口中的旧字符。时间复杂度为O(n)。
代码如下：
def lengthOfLongestSubstring(s: str) -> int: n = len(s) ans = 0 lookup = {} i = 0 for j in range(n): if s[j] in lookup: i = max(lookup[s[j]], i) ans = max(ans, j - i + 1) lookup[s[j]] = j + 1 return ans
无论使用哪种算法，它们的时间复杂度都为O(n)，其中 n 是字符串的长度。
