1. 给定一个字符串 s ,请你找出其中不含有重复字符的 最长 子串的长度
时间: 2024-09-19 18:02:42 浏览: 39
js代码-给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
这个问题可以使用滑动窗口(Sliding Window)算法来解决。滑动窗口是一种常用的动态规划思想,通常用于处理数组或字符串中的连续子序列问题。以下是基本思路:
1. 初始化两个指针 left 和 right,分别指向字符串的开始位置,同时创建一个集合(或哈希表)存储已经遇到过的字符。
2. 遍历字符串 s,如果当前字符不在集合中,将其添加到集合,并将 right 指针右移一位,更新最长无重复字符子串的长度(即 right - left + 1)。
3. 如果当前字符已经在集合中,说明遇到了重复字符,此时从集合中删除左边界指针所对应的字符,然后将 left 指针右移一位,继续检查下一个字符。
4. 在遍历过程中,不断更新最长子串的长度,直到遍历完整个字符串。
5. 最终返回最长无重复字符子串的长度。
下面是伪代码示例:
```python
def lengthOfLongestSubstring(s):
max_len = 0
visited = set()
left = 0
for right in range(len(s)):
if s[right] not in visited:
visited.add(s[right])
max_len = max(max_len, right - left + 1)
else:
visited.remove(s[left]) # 移除重复字符
left += 1
return max_len
```
阅读全文