题目

题目详情

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题代码

思路

1. 如果需要查找到最长的子串，那么久需要记录子串的位置，值，以及长度。
2. 那么我们直接用到字典，字典可以记录子串的位置，以及值
3. 如abcabcd，字典中会存下a，b，c分别的值和位置，后面遇到的时候会更新他们新的位置，以便d能够以连续的位置存下。

代码

class Solution:def lengthOfLongestSubstring(self,s):dic = {}i , length = 0 , 0for j in range(len(s)):if s[j] in dic:i = max(dic[s[j]] , i)   #最长子串的初始位置length = max(length,j-i+1)   #求最长子串的长度dic[s[j]] = j + 1            #最长子串的值和位置return length

运行结果

最佳方案

用时64ms的最快的一个解决方案：

class Solution:def lengthOfLongestSubstring(self, s: 'str') -> 'int':start = best = 0checked = {}for i in range(0, len(s)):if s[i] in checked and checked[s[i]] >= start:start = checked[s[i]] + 1else:if i+1-start > best:best = i+1-startchecked[s[i]] = ireturn best