Longest Substring Without Repeating Characters

Problem

A password validation service needs to find the longest contiguous run of unique characters in a candidate string. This length is used as a uniqueness score. Given a string, return the length of the longest substring that contains no repeating characters.

Input: "abcabcbb"  → 3   ("abc")
Input: "bbbbb"     → 1   ("b")
Input: "pwwkew"    → 3   ("wke")
Input: ""          → 0

Solution

Approach: Variable-size sliding window with a character frequency map.

Expand the window one character at a time from the right and keep it valid by shrinking from the left whenever a duplicate appears. A char_count dict records how many times each character sits inside the current window [start, end]. For each end, increment char_count[s[end]]. If that count just became 2, the new character is a duplicate, so run the inner while char_count[s[end]] > 1 loop: decrement char_count[s[start]] and advance start until the duplicate's count falls back to 1. At that point every character in the window is unique again, so record best = max(best, end - start + 1). The window length is end - start + 1 because both indices are inclusive. Shrinking only to a count of 1 (not 0) is deliberate - you remove just enough copies to eliminate the duplicate, keeping the window as long as possible.

Trace "abcabcbb": the window grows to "abc" (best 3). The second "a" enters, so start advances past the first "a", leaving "bca" - still length 3. This repeats, and best stays 3, the right answer.

Edge cases: The empty string returns 0 because the outer loop never runs and best starts at 0. A string of all identical characters shrinks to size 1 each step.

Complexity: O(n) time, O(min(n, alphabet)) space - start only moves forward so total advances are at most n, and the map holds at most one entry per distinct character.