Leetcode 3. Longest Substring Without Repeating Characters-蒲公英云

Leetcode 3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"
Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

字符串简单题。Sliding window + set / dict
基础算法是把把char都放到一个set里，left指针按照步长为1往右移动并判重。
优化算法是出现重复时，直接把window右移到不重复位置再继续，即left指针移动到重复位置+1。
- https://leetcode.com/problems/longest-substring-without-repeating-characters/solution/
- The above solution requires at most 2n steps. In fact, it could be optimized to require only n steps. Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.
- The reason is that if s[j] have a duplicate in the range [i, j) with index j’, we don’t need to increase i little by little. We can skip all the elements in the range [i, j’] and let i to be j’ + 1 directly.
Python3 字典 | 菜鸟教程
- http://www.runoob.com/python3/python3-dictionary.html
Python3 集合 | 菜鸟教程
- http://www.runoob.com/python3/python3-set.html

1 class Solution:
 2     def lengthOfLongestSubstring(self, s: str) -> int:
 3         d = dict()  # current index of character        
 4         left, right, maxlen = 0, 0, 0
 5         n = len(s)
 6         
 7         while right < n:
 8             # if char in dict[j']，skip all the elements in the range [i,j'] and let i to be j'+1 directly.
 9             if s[ right ] in d:
10                 left = max( d[ s[ right ] ], left ) 
11 
12             maxlen = max( right - left + 1, maxlen )
13 
14             # set next available index for left, i.e. j'+1
15             d[ s[ right ] ] = right + 1
16 
17             right += 1
18                 
19         return maxlen
20     
21     def lengthOfLongestSubstring1(self, s: str) -> int:
22         dict = set()
23         
24         n = len(s)
25         left, right, maxlen = 0, 0, 0
26         
27         while right < n:
28             if s[ right ] not in dict:
29                 dict.add( s[ right ] )
30                 maxlen = max( maxlen, right - left + 1 )
31                 right += 1
32             else:
33                 dict.remove( s[ left ] )
34                 left += 1                
35                 
36         return maxlen