FIND THE LONGEST RUN OF CHARACTERS WITH NO REPEAT. SLIDE A WINDOW RIGHT, AND WHEN A CHARACTER REPEATS INSIDE IT, JUMP THE LEFT EDGE PAST THE OLD COPY SO THE WINDOW STAYS CLEAN.
A WINDOW WITH NO REPEAT CAN ONLY GROW BY MOVING RIGHT. WHEN THE NEXT CHARACTER IS ALREADY INSIDE, SLIDE THE LEFT EDGE JUST PAST THE OLD COPY SO THE WINDOW IS CLEAN AGAIN. THE LONGEST WINDOW EVER SEEN IS THE ANSWER.
THE GREEN TILES ARE THE CURRENT WINDOW, GOLD ON A NEW BEST. L AND R MARK ITS ENDS. A REPEAT INSIDE REDDENS THE OLD COPY AND JUMPS L PAST IT. A REPEAT ALREADY BEHIND L IS IGNORED BY THE GUARD. THE SEEN SHELF HOLDS THE LAST INDEX OF EACH CHARACTER.
1def length_of_longest_substring(s):2 max_l = 03 substrings = {}4 l = 05 for r in range(len(s)):6 c = s[r]7 if c in substrings and substrings[c] >= l:8 l = substrings[c] + 19 substrings[c] = r10 max_l = max(max_l, r - l + 1)11 return max_l
EACH OF L AND R MOVES FORWARD ONLY, SO THE STRING IS WALKED ONCE.
THE SEEN MAP HOLDS ONE INDEX PER DISTINCT CHARACTER, AT MOST THE ALPHABET SIZE.