Python代码实现:最长不重复子串问题:给定一个字符串S,返回S中所有字符的最长不重复子串的长度。如果S为空,返回0。
时间: 2023-05-24 21:06:37 浏览: 57
示例:
输入: "abcabcbb"
输出: 3
解释: 最长的不重复子串是 "abc",其长度为3。
输入: "bbbb"
输出: 1
解释: 最长的不重复子串是 "b",其长度为1。
输入: ""
输出: 0
代码实现:
```python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:
return 0
left = res = 0
lookup = set()
for right in range(len(s)):
while s[right] in lookup:
lookup.remove(s[left])
left += 1
lookup.add(s[right])
res = max(res, right - left + 1)
return res
```
解析:
使用一个滑动窗口来维护最长的不重复子串。初始时,窗口左右端点都指向字符串的起始位置。然后逐个向右移动右端点,并将右端点指向的字符加入到集合中。
如果当前字符已经在集合中存在,说明窗口中已经存在重复字符,那么就需要从窗口左端点开始移动,并将左端点指向的字符从集合中删除,直到窗口中不再有重复的字符。
在移动窗口的过程中,我们需要不断地记录最长的不重复子串的长度,并更新结果res。
时间复杂度:O(n)
空间复杂度:O(n)