给定一个字符串,找到最长的字串,使得该字串中的字符都不重复
时间: 2024-12-12 18:22:56 浏览: 14
C语言求两个字符串的最长公共子串
这个问题可以通过滑动窗口(Sliding Window)技术来解决。我们可以从字符串的第一个字符开始,维护一个大小为已知唯一字符数量的窗口,并向右移动窗口,同时检查新加入的字符是否与窗口内的字符重复。如果不重复,就将窗口扩大;如果重复,就收缩窗口直到重复的字符被移出。最后,记录并更新最长无重复字符的子串长度。
以下是一个Python的解决方案:
```python
def lengthOfLongestSubstring(s):
if not s:
return 0
# 使用两个指针:left表示窗口的起始位置,right表示窗口的结束位置
left = 0
max_length = 0
chars_used = set() # 存储当前窗口内已使用的字符
for right in range(len(s)):
while s[right] in chars_used: # 如果右边界字符在已使用字符集中
chars_used.remove(s[left]) # 移除左边界对应的字符
left += 1 # 左边界向右移动一位
chars_used.add(s[right]) # 将右边界字符添加到已使用字符集中
max_length = max(max_length, right - left + 1) # 更新最长子串长度
return max_length
# 测试例子
s = "pwwkew"
print(lengthOfLongestSubstring(s)) # 输出:3,因为最长无重复字符的子串是"wke"
```
阅读全文