给定—个字符串s,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入:s= "abcabcbb" 输出:3 解释:因为无重复字符的最长子串是“abc',所以其长度为 3。 示例2: 输入:S="bbbbb" 输出:1 解释:因为无重复字符的最长子串是“6”,所以其长度为 1。 示例 3: 输入:s="pwwkew" 输出:3 解样:因为无重复字符的最长子串是“wke',所以其长度为 了。 请注意,你的答案化须是 子串 的长度,“pwke”是一个子序列,不是子串。用python实现
时间: 2024-02-01 11:16:44 浏览: 22
可以使用滑动窗口的思想来解决这个问题。具体步骤如下:
1. 定义一个哈希表,用来存储每个字符最后一次出现的位置。
2. 定义两个指针left和right,分别指向子串的左右边界。
3. 遍历字符串,如果当前字符不在哈希表中,将其加入哈希表,并将right指针向右移动一位;如果当前字符已经在哈希表中,需要更新left指针的位置,使其指向上一次出现该字符的位置的下一位,并更新哈希表中该字符的位置。
4. 在遍历过程中不断更新最长子串的长度。
最终,最长无重复字符子串的长度即为所求。
代码如下:
```python
def lengthOfLongestSubstring(s: str) -> int:
if not s:
return 0
char_dict = {} # 哈希表,用来记录每个字符最后一次出现的位置
left, right = 0, 0 # 滑动窗口的左右边界
max_len = 0 # 最长子串的长度
for i in range(len(s)):
if s[i] in char_dict and char_dict[s[i]] >= left:
# 当前字符已经在哈希表中,并且上一次出现的位置在left和right之间
left = char_dict[s[i]] + 1
char_dict[s[i]] = i # 更新当前字符的位置
right = i # 右指针向右移动一位
max_len = max(max_len, right - left + 1) # 更新最长子串的长度
return max_len
```