Longest Substring Without Repeating Characters

Intuition

A repeat-free window is defined entirely by its left boundary: as soon as the incoming character was seen inside the current window, the boundary must move just past that earlier occurrence. Storing each character's latest position lets the left edge leap directly to the right spot instead of stepping one by one, so the whole string is scanned once while the window length is tracked at every step.

Algorithm walkthrough

1. 1Keep a map from character to the last index where it appeared, and a left pointer marking the window start.
2. 2Walk the right pointer across the string one character at a time.
3. 3If the current character was seen at or after the left pointer, move left to one past that stored index.
4. 4Record the current index for the character and update the best length with the current window size.
5. 5After the scan finishes, the best length is the answer.

Implementation

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = {}
        left = 0
        best = 0
        for right, ch in enumerate(s):
            if ch in last and last[ch] >= left:
                left = last[ch] + 1
            last[ch] = right
            best = max(best, right - left + 1)
        return best