leetcode/substringlength.py at main · IongIer/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from collections import deque


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        length = len(s)
        if length == 0 or length == 1:
            return length

        # you don't need both a queue and a set here, there is a better solution
        seen = deque()
        unique = set()
        curr = 0
        best = 0
        for v in s:
            if v in unique:
                best = max(best, curr)
                while seen:
                    rem = seen.popleft()
                    unique.remove(rem)
                    if rem == v:
                        break
                seen.append(v)
                unique.add(v)
                curr = len(seen)

            else:
                unique.add(v)
                seen.append(v)
                curr = len(seen)
                best = max(curr, best)
        return max(best, curr)