3. Longest Substring Without Repeating Characters

Medium

13757711Add to ListShare

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

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

Input: s = ""
Output: 0

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """
        思路：从下标0开始枚举字符保存到字符串里，直到找到一个字符在之前的字符串里出现过，
        更新最长子串长度，然后从之前出现过得字符下标的下一位开始枚举，因为之前的必不可能比当前已知的更长
        时间最好o(n) 最坏o(n^2)
        
        如：abcabcbb
        abc[a]
        bca[b]
        cab[c]
        abc[b]
        cb[b]
        """
        max_len = 1
        left, right = 0, 1

        while left < len(s):
            if right >= len(s):
                return max(max_len, right - left)
            c = s[right]
            sub_string = s[left: right]
            if c in sub_string:
                index = sub_string.find(c)
                max_len = max(max_len, right - left)
                left += index + 1
                right = left + 1
                continue
            right += 1
        return 0