给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度
时间: 2023-10-14 13:10:46 浏览: 100
js代码-给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
这是一个经典问题,可以使用滑动窗口算法来解决。
具体思路如下:
1. 定义一个窗口,用来存储不重复的字符。
2. 定义两个指针 left 和 right,分别指向窗口的左右边界。
3. 循环遍历字符串 s,每次将 right 指针向右移动一位,并将对应的字符加入窗口中。
4. 如果加入字符后窗口中出现了重复字符,则将 left 指针向右移动,直到窗口中不再出现重复字符。
5. 每次移动指针时,记录窗口的大小,并更新最大窗口大小。
6. 循环遍历完字符串 s 后,最大窗口大小即为所求的最长子串长度。
以下是示例代码实现:
```python
def lengthOfLongestSubstring(s: str) -> int:
left, right = 0, 0
max_len = 0
window = set()
while right < len(s):
if s[right] not in window:
window.add(s[right])
right += 1
max_len = max(max_len, len(window))
else:
window.remove(s[left])
left += 1
return max_len
```
时间复杂度为 O(n),空间复杂度为 O(k),其中 k 为字符集大小。
阅读全文