Leetcode 3. Longest Substring Without Repeating Characters

超、凢脫俗 2021-12-22 00:55 184阅读 0赞

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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

转载于:https://www.cnblogs.com/pegasus923/p/10452148.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/7da9faaab6d14b41891cc4235a0fbd28.png