#3 Longest Substring Without Repeating Characters——Top 100 Liked Questions

一时失言乱红尘 2022-04-24 15:44 108阅读 0赞

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.

> """
> 
> 第一次：依次遍历字符串，若不存在，加到tmp中；若某字符存在，用count记录不重复字符串长度，用result保存不重复字符串，每次遇到重复字符时，判断当前不重复字符串与上一不重复字符串哪个更长，并在count和result中保存较长的，同时将tmp中与该字符相同的字符位置之前（包括该字符）的字符清空，
> 
> """
> 
> class Solution(object):  
>     def lengthOfLongestSubstring(self, s):  
>         """  
>         :type s: str  
>         :rtype: int  
>         """  
>         if len(s) == 0: return 0  
>         if s.count(s\[0\]) == len(s): return 1  
>         tmp = \[\]  
>         result = \[\]  
>         for string in s:  
>             if string not in tmp:  
>                 tmp.append(string)  
>             else:  
>                 if len(result) < len(tmp):  
>                     result = tmp  
>                 index = tmp.index(string)  
>                 tmp = tmp\[index + 1:\]  
>                 tmp.append(string)  
>         return max(len(result), len(tmp))
> 
> """
> 
> Runtime: 64 ms, faster than 51.21% of Python online submissions for Longest Substring Without Repeating Characters.
> 
> Memory Usage: 12.2 MB, less than 9.60% of Python online submissions for Longest Substring Without Repeating Characters.
> 
> """