给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度
时间: 2023-10-14 20:16:03 浏览: 113
你的问题可以通过使用滑动窗口算法来解决。具体实现如下:
1. 定义一个字典来存储字符和它们在字符串中的最近一次出现的索引。
2. 定义两个指针 left 和 right,分别指向子串的左右边界。
3. 当右指针指向的字符在字典中已经存在时,更新左指针的位置为该字符在字典中的最近一次出现的索引加1。
4. 在遍历过程中,记录每个不重复子串的最大长度,并返回该长度。
以下是实现代码:
```
def lengthOfLongestSubstring(s: str) -> int:
char_dict = {} # 存储每个字符及其最近一次出现的索引
left = 0 # 左指针,子串左边界
max_len = 0 # 不重复子串的最大长度
for i, char in enumerate(s):
if char in char_dict and char_dict[char] >= left:
left = char_dict[char] + 1
char_dict[char] = i
max_len = max(max_len, i - left + 1)
return max_len
```
你可以使用该函数进行测试:
```
s = "abcabcbb"
print(lengthOfLongestSubstring(s)) # 输出3,对应的不重复子串为"abc"
s = "bbbbb"
print(lengthOfLongestSubstring(s)) # 输出1,对应的不重复子串为"b"
s = "pwwkew"
print(lengthOfLongestSubstring(s)) # 输出3,对应的不重复子串为"wke"
s = ""
print(lengthOfLongestSubstring(s)) # 输出0,空字符串不存在不重复子串
s = " "
print(lengthOfLongestSubstrng(s)) # 输出1,空格""为不重复子串
```
阅读全文