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: 1Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"Output: 3Explanation: 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'+115             d[ s[ right ] ] = right + 116 17             right += 118                 19         return maxlen20     21     def lengthOfLongestSubstring1(self, s: str) -> int:22         dict = set()23         24         n = len(s)25         left, right, maxlen = 0, 0, 026         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 += 132             else:33                 dict.remove( s[ left ] )34                 left += 1                35                 36         return maxlen