前言

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
那就開始今天的解題吧~

Question

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.

Constraints:

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

Think

給一個字串s，找出其中最長的沒有重複字元的子字串~

• 用兩個index(index1, index2)，每次迴圈會得到一個子字串substring = s[index1:index2+1]
• 如果len(substring) > len(set(substring))代表說這個子字串有重複的字元，index1就後一格，index2則是以index1的新位置再多往後移目前最長的子字串(max_len)(因為至少要比max_len長才有跑這一段的必要)，如果移完index2超出範圍就直接return max_len。
• 另一種就是len(substring) == len(set(substring))，表示是不重複字元的子字串，如果index2不是最後一個了，就讓index1固定不動，max_len跟index2都加1，繼續往後找有沒有更長的子字串。

Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        #print("len: ", len(s))
        if len(s) <= 1:
            return len(s)

        index1 = 0
        index2 = 1
        max_len = 1

        while index1 <= len(s):
            substring = s[index1:index2+1]
            #print("sub: ", substring)
            if len(substring) > len(set(substring)):
                #print("repeat")
                index1 += 1
                index2 = index1 + max_len
                if index2 > len(s)-1:
                    return max_len
            else:
                #print("unique")
                if index2 == len(s)-1:
                    index1 += 1
                    index2 = index1 + max_len
                    max_len += 1
                    if index2 > len(s)-1:
                        return max_len
                else:
                    max_len += 1
                    index2 += 1

        return max_len 

Submission

今天就到這邊啦~
大家明天見