首页 > 代码库 > Leetcode 3. Longest Substring without repeating characters

Leetcode 3. Longest Substring without repeating characters

思路:类似双指针,用left标定以当前字母结尾的最长无重的substring的起点。逐个扫描字母,如果这个字母当前的substring里面没有,那么当前的substring长度就可以加一。如果这个字母已经在substring里面了,例如:

技术分享

当扫描到第二个c的时候,left应该移到d上来。并且应该将 C:2 更新为 C:6。 这里由于需要第一个c 的index,应该使用一个hash table。 如果cur后面又出现了一个a,由于目前a这个key的value小于left,所以说明current non repeating substring里面没有a。注意L14的条件。

 1 class Solution(object):
 2     def lengthOfLongestSubstring(self, s):
 3         """
 4         :type s: str
 5         :rtype: int
 6         """
 7         
 8         ans = 0
 9         left = 0
10         
11         curStr = {}
12         
13         for i in range(len(s)):
14             if s[i] in curStr and curStr[s[i]] >= left:
15                 left = curStr[s[i]] + 1
16             
17             curStr[s[i]] = i
18             
19             ans = max(ans, i-left +1)
20         
21         return ans
22                 

 

Leetcode 3. Longest Substring without repeating characters