用python打出下列条件的程序,给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
时间: 2023-06-20 08:10:25 浏览: 103
python 实现给定一个字符串,找出不含有重复字符的最长子串的长度
5星 · 资源好评率100%
可以使用滑动窗口的方法来解决这个问题。具体步骤如下:
1. 定义一个双指针 left 和 right,表示当前子串的左右边界;
2. 定义一个字典 used_chars,用来记录已经出现过的字符及其在子串中的位置;
3. 初始化 left = 0,right = 0,max_len = 0;
4. 从左到右遍历字符串 s,每次将 right 向右移动一位,并将当前字符 s[right] 添加到 used_chars 中;
5. 如果当前字符 s[right] 已经在 used_chars 中出现过,并且它的位置在 left 和 right 之间(即在当前子串中),则更新 left 的值为 used_chars[s[right]] + 1,表示将左边界移动到重复字符的下一个位置;
6. 计算当前子串的长度 max_len,并更新最大长度 max_len;
7. 重复步骤 4-6,直到 right 到达字符串 s 的末尾。
下面是具体的 Python 代码实现:
```python
def lengthOfLongestSubstring(s: str) -> int:
used_chars = {}
left = 0
right = 0
max_len = 0
while right < len(s):
if s[right] in used_chars and used_chars[s[right]] >= left:
left = used_chars[s[right]] + 1
used_chars[s[right]] = right
max_len = max(max_len, right - left + 1)
right += 1
return max_len
```
这个函数接受一个字符串 s 作为参数,并返回最长不含重复字符的子串的长度。例如:
```python
print(lengthOfLongestSubstring("abcabcbb")) # 3
print(lengthOfLongestSubstring("bbbbb")) # 1
print(lengthOfLongestSubstring("pwwkew")) # 3
print(lengthOfLongestSubstring("")) # 0
```
阅读全文