Longest Substring Without Repeating Characters

Prompt

We're scanning a stream of session tokens and want the longest run with no repeated character — a cheap signal for how varied a chunk is. Given a string, return the length of the longest substring with all distinct characters.

How this round runs

I haven't pinned down the character set or whether you need the substring itself or just its length — clarify before coding, and expect me to generalize the constraint once the basic version works.

Model answer

Clarify first: what's the alphabet — ASCII, Unicode? Do I return just the length, or the actual substring? Is the empty string a valid input (answer 0)?

Brute force checks every substring for uniqueness — O(n^2) or worse. The efficient move is a sliding window: keep a window [left, right] that holds only distinct characters. Walk right forward; when the new character was last seen inside the window, jump left to just past that previous index. A last-seen map gives O(1) lookups, so it's one pass — O(n) time, and O(min(n, alphabet)) space.

function longestUnique(s) {
  const lastSeen = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (lastSeen.has(ch) && lastSeen.get(ch) >= left) {
      left = lastSeen.get(ch) + 1; // shrink past the duplicate
    }
    lastSeen.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

The >= left guard matters: a stale index from before the window must not drag left backward. We move left to the duplicate's index plus one — not just +1 — so the window jumps in one step instead of crawling.

Dry-run on "abcabcbb": window grows to abc (3); the second a pushes left past index 0; it keeps sliding, never beating 3, so the answer is 3.

Signals — what a strong answer shows

Asked about the character set and whether the substring or just its length is needed
Named the brute force, then the sliding window with a last-seen map
Moved left to previous-index + 1 and guarded against a stale index (>= left)
Stated O(n) time, O(min(n, alphabet)) space, and dry-ran a string with repeats

Follow-ups — where it goes next

Now allow at most k distinct characters instead of all-unique → same window, but shrink from the left while the distinct-count exceeds k
Return the substring itself, not the length → track the window's start index whenever you update the best length

Study this: Algorithms