unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 3. Longest Substring Without Repeating Characters

link

We use sliding window. Until we find a repeated character in the current window, we keep expanding. Say our current window is s[begin : end] and we see s[end] at index i, where i >= begin. Then our new window is: s[i+1 : end+1] — once again, the window has all unique characters.

Time: \mathcal{O}(n), space: \mathcal{O}(n).

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = 0
        last_seen_at = {}
        begin = 0
        for end, c in enumerate(s):
            if (pos := last_seen_at.get(c, -1)) >= begin:
                begin = pos + 1
            else:
                max_len = max(max_len, end-begin+1)
            
            last_seen_at[c] = end
        
        return max_len

tanvirdotzaman

,

Leave a comment