给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 例如 输入: abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是"abc",所以其长度为 3。
时间: 2023-10-14 22:25:55 浏览: 93
python 实现给定一个字符串,找出不含有重复字符的最长子串的长度
5星 · 资源好评率100%
好的,这是一道经典的算法题,通常被称为无重复字符的最长子串(Longest Substring Without Repeating Characters)问题。以下是一个解题思路:
1. 创建一个字典,用于存储每个字符最后一次出现的位置。
2. 创建两个指针 i 和 j,分别指向子串的起始位置和结束位置,初始化为 0。
3. 遍历整个字符串,对于每个字符,如果它之前出现过,并且出现位置在当前子串的范围内(即在 i 和 j 之间),则更新 i 为该字符上一次出现的位置的下一个位置,否则计算当前子串的长度(即 j-i+1),并更新最长子串的长度。
4. 更新当前字符的位置为 j+1,继续遍历下一个字符。
下面是一个简单的 Python 代码实现:
```
def lengthOfLongestSubstring(s):
char_dict = {}
max_len = 0
i = 0
for j in range(len(s)):
if s[j] in char_dict and char_dict[s[j]] >= i:
i = char_dict[s[j]] + 1
char_dict[s[j]] = j
max_len = max(max_len, j-i+1)
return max_len
```
这个函数接受一个字符串作为输入,返回一个整数,表示该字符串中不含有重复字符的最长子串的长度。
阅读全文