• 分類：HashTable

• 考察知識點：HashTable String

• 最優(yōu)解時間復(fù)雜度：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:
                # 找最長的不重復(fù)字符的字符串
                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