LeetCode 3 Longest Substring Without Repeating Characters - Example and Complexity Analysis

Trace s = "pwwkew".

Initialize: left = 0, maxLen = 0, seen = {}.

right = 0: 'p' not in window. seen = {p: 0}. Window = "p". maxLen = 1.

right = 1: 'w' not in window. seen = {p: 0, w: 1}. Window = "pw". maxLen = 2.

right = 2: 'w' in window at 1. Move left = 2. Update seen[w] = 2. Window = "w".

right = 3: 'k' not in window. Window = "wk". maxLen = 2.

right = 4: 'e' not in window. Window = "wke". maxLen = 3.

right = 5: 'w' in seen at 2, but 2 < left = 2 is false. Move left = 3. Window = "kew". maxLen = 3.

Return 3.

Each character enters and exits the window at most once. $O(n)$ time. Hash map stores at most $k$ characters. $O(k)$ space.