longest unrepeated substring

Longest substring without repeated characters

The two ideas for this problem are either to perform a traversal to solve it violently, or to perform a sliding window (cleverly), and we'll look at the violent solution first below:

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

        s_count = len(s)

        max_list = []
        if s_count == 0:
            return 0
        else:
            # Two levels of traversal
            for i in range(s_count):
                tmp = s[i]
                max_list.append(tmp)
                for j in range(i+1, s_count):
                    tmp += s[j]
                    max_list.append(tmp)
            # Then use set to determine if there are any duplicates in the substring.
            return max([len(i) for i in max_list if len(set(list(i))) == len(i)])

This time complexity is N-square, look at the following sliding window solution, I come to a left and right, and then traverse with the right, if there is a duplicate substring, I delete the left, know that there is no duplicate until, this idea is too can.

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

        left = 0

        s_len = len(s)
        max_count = 0
        # Use set to record the longest non-repeating substring.
        max_set = set()
        # right traverses s
        for right in range(s_len):
            # If I'm in a set, I delete the left one until there are no more duplicates.
            while s[right] in max_set:
                max_set.remove(s[left])
                left += 1
            max_set.add(s[right])

            max_count = max(max_count, right - left + 1)
        return max_count

The time complexity of the sliding window is O(N), which improves quite a bit.