python最长不重复子串问题:给定一个字符串S,返回S中所有字符的最长不重复子串的长度。如果S为空,返回0。 例如: 输入:S = “abcabcbb” 输出:3 解释:最长不重复子串是"abc",长度为3。 输入:S = “bbbbb” 输出:1 解释:最长不重复子串是"b",长度为1。
时间: 2023-05-15 15:08:04 浏览: 67
可以使用滑动窗口算法来解决这个问题。具体来说,我们可以使用两个指针left和right来表示当前考虑的子串的左右边界,使用一个哈希表来记录每个字符最后一次出现的位置。初始时,left和right都指向字符串的开头,哈希表为空。然后,我们不断地将right向右移动,直到遇到一个重复的字符。此时,我们可以更新最长不重复子串的长度,并将left指向重复字符的下一个位置。同时,我们需要将哈希表中所有在left之前的字符的位置信息删除,以确保我们只考虑当前子串中的字符。最后,我们将right继续向右移动,重复上述过程,直到right到达字符串的末尾。
以下是Python代码实现:
def lengthOfLongestSubstring(s: str) -> int:
n = len(s)
if n == 0:
return 0
left, right = 0, 0
max_len = 0
char_dict = {}
while right < n:
if s[right] in char_dict and char_dict[s[right]] >= left:
left = char_dict[s[right]] + 1
char_dict[s[right]] = right
max_len = max(max_len, right - left + 1)
right += 1
return max_len
输入:S = “abcabcbb”
输出:3
解释:最长不重复子串是"abc",长度为3。
输入:S = “bbbbb”
输出:1
解释:最长不重复子串是"b",长度为1。