Leetcode 3. longest substring without repeated characters

Power button | 3. Longest substring without repeating characters

Title screenshot

Method 1 ： Violence law

Use the list . Use list slices to slide windows .

Traversal string s, Constantly add the characters of the string to the list .

If a new element in the string is found in the previous list , Use slices now , Cut the beginning of the slice to the last bit of the repeating element , Then add the repeating element （ At this time, the repeated part has been cut off ）, Then continue to traverse down .

Each addition compares the length , Choose the longer one , Finally, the maximum substring length is returned .

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        a = []
        res = 0
        for i in s:
            if i in a:
                a = a[a.index(i)+1:]
            a.append(i)
            res=res if len(a)< res else len(a)
        return res

res It can be used directly max() function

res = max(res, len(a))

Complete test code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        a = []
        res = 0
        for i in s:
            if i in a:
                a = a[a.index(i)+1:]
            a.append(i)
            res=res if len(a)< res else len(a)
        return res

class main():
    a = Solution()
    s = "abcabcbb"
    print(a.lengthOfLongestSubstring(s))

if __name__ == '__main__':
    main()

Method 2 ： Slide window one

set() Function can create a set of non repeating elements , This function can be used to determine whether there is a repeated part .

Python set() function | Novice tutorial

The inner loop determines whether the newly added element is repeated , If it does not repeat, the pointer moves to the right , Add it to the element set . If the newly added element repeats and cannot enter the loop , Jump out of the loop and enter the outer loop , The outer loop will delete the previous elements , This element is a previously repeated element .

In this way, a series of substrings can be found by using the left and right pointer sliding window , utilize max() Function returns the largest substring without repetition .

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        #  Hash set , Record whether each character appears 
        occ = set()
        n = len(s)
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                occ.add(s[rk + 1])
                rk += 1
            ans = max(ans, rk - i + 1)
        return ans

Method 3 ： Sliding window II

The basic idea is the same as the above, with a little difference . It's easier to understand .

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        occ = set()
        left = 0
        max_len, cur_len = 0, 0
        n = len(s)
        for i in range(n):
            cur_len += 1
            while s[i] in occ:
                occ.remove(s[left])
                left += 1
                cur_len -= 1
            max_len = max(max_len, cur_len)
            occ.add(s[i])
        return max_len