• 分类：HashTable

• 考察知识点：HashTable String

• 最优解时间复杂度：O(n)

3. Longest Substring Without Repeating Characters

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

Example1:

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

Example2:

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

Example2:

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.

代码：

解法:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        length = 0

        if s==None or s=="":
            return length

        start = 0
        char_dict = dict()
        for end in range(len(s)):
            if s[end] in char_dict:
                # 找最长的不重复字符的字符串
                start = max(start, char_dict[s[end]]+1)
            char_dict[s[end]] = end
            # 找这些字符串里最大的
            length = max(length, end-start+1)
        
        return length

讨论：

1.看到Without repeatedly啥的，记得用Hash Table，在Python中就是dictionary
2.j是新的一段的开头，一定要记住** j=max(j,d[n]+1)**,不能让它回到前面去

WechatIMG1626.jpeg