首页最长不含重复字符的子字符串python

最长不含重复字符的子字符串python

时间: 2023-10-19 11:04:43 浏览: 103

可以使用滑动窗口来解决这个问题，具体实现如下： ```python def longest_substring_without_repeating_characters(s): n = len(s) ans = 0 left = 0 right = 0 seen = set() # 用集合存储已经出现的字符 while left < n and right < n: if s[right] not in seen: seen.add(s[right]) right += 1 ans = max(ans, right - left) # 更新答案 else: seen.remove(s[left]) left += 1 return ans ``` 首先，定义三个变量 `left`、 `right` 和 `seen`，其中 `seen` 是一个集合，用于存储已经出现的字符。然后，我们不断移动右指针 `right`，如果当前字符不在 `seen` 中，就将其加入 `seen` 中，并更新答案；如果当前字符在 `seen` 中，就移动左指针 `left`，并将左指针指向的字符从 `seen` 中移除。最终，我们得到的答案就是最长的不含重复字符的子字符串的长度。例如，对于字符串 `"abcabcbb"`，我们可以按以下步骤进行处理： 1. 初始化 `left = 0`、 `right = 0`、 `seen = set()`、 `ans = 0`； 2. 当 `right < n` 时，比较 `s[right]` 是否在 `seen` 中： - 如果不在，将 `s[right]` 加入 `seen` 中，更新 `right = right + 1` 和 `ans = max(ans, right - left)`； - 如果在，将 `s[left]` 从 `seen` 中移除，更新 `left = left + 1`； 3. 返回 `ans = 3`。因为最长的不含重复字符的子字符串是 `"abc"`，长度为 3，所以得到的答案是 3。

阅读全文