Leetcode 3. Longest Substring Without Repeating Characters

給定一個字串,在不重複字符的情況下尋找最長子字串。

想法

移動窗口

使用一個字典檔紀錄目前有出現過的字串符,利用變數j紀錄加到字符的哪個索引,當字符重複添加時,從變數i開始拿出字符,持續變更i,直到沒有重複再繼續從變數j繼續添加字符重複動作直到結尾。
程式碼：

def lengthOfLongestSubstring(self, s: str) -> int:
        if(len(s)<=1):
            return len(s)
        s_dict = {}
        i = 0
        s_dict[s[i]] = 1
        ans = 0
        j = i+1
        while(j<len(s)):
            if(s[j] in s_dict):
                s_dict[s[i]] -=1
                ans = max(j-i,ans)
                if(s_dict[s[i]]==0):
                    del s_dict[s[i]]
                i+=1
            else:
                s_dict[s[j]] = 1
                j+=1
        ans = max(j-i,ans)
        return ans