Longest Substring Without Repeating Characters — #3

If there is one problem that teaches the sliding window pattern better than any other, it is Longest Substring Without Repeating Characters. LeetCode #3 sits comfortably in the top five most-asked Medium problems across all major tech companies, and for good reason — it perfectly demonstrates how a simple two-pointer technique can turn an expensive brute force into an elegant linear solution.

Most engineers first encounter sliding window through this exact problem. The concept is straightforward: given a string, find the length of the longest substring where every character is unique. But the jump from understanding the problem to writing an optimal solution is where the real learning happens.

This walkthrough covers three approaches — brute force, sliding window with a Set, and the HashMap optimization — so you understand not just what works, but why each improvement matters. By the end, you will own a pattern that applies to dozens of other interview problems.

The problem statement is deceptively simple. Given a string s, find the length of the longest substring without repeating characters. A substring is a contiguous sequence of characters within the string — not a subsequence, which can skip characters.

For the input "abcabcbb", the answer is 3 because "abc" is the longest substring with all unique characters. For "bbbbb", the answer is 1 — the best you can do is a single character. For "pwwkew", the answer is 3 from "wke" or "kew".

The key constraint is that every character in your window must appear exactly once. The moment a duplicate enters, you need to shrink or reset. This constraint is what makes the problem a perfect fit for the sliding window pattern.

The most intuitive approach is to check every possible substring and find the longest one with all unique characters. For each starting index i, you expand to every ending index j and verify uniqueness. This gives you O(n^2) substrings to check, and verifying each one takes O(n) in the worst case with a scan, or O(1) amortized with a Set.

With a nested loop and a Set for uniqueness checking, the brute force runs in O(n^2) time. For each starting position, you add characters to a Set one by one. The moment you find a duplicate, you record the current window length and move to the next starting position.

This approach works for small inputs but fails on strings of length 50,000. The quadratic time complexity means roughly 2.5 billion operations in the worst case. Interviewers expect you to identify this inefficiency and optimize.

The critical insight is that when you find a duplicate at position j, you do not need to restart from i+1. The characters between i and the first occurrence of the duplicate are still valid — you just need to slide past the duplicate. This observation leads directly to the sliding window approach.

The sliding window approach maintains two pointers, left and right, that define your current substring. You expand right to include new characters and shrink left to remove duplicates. A Set tracks which characters are currently in your window, giving you O(1) lookup for duplicates.

Start with both pointers at index 0 and an empty Set. Move right one step at a time. If the character at right is not in the Set, add it and update your maximum length. If it is already in the Set, remove the character at left from the Set and advance left. Repeat until right is no longer a duplicate, then continue expanding.

Each character enters the Set at most once and leaves the Set at most once, so the total work across all iterations is O(n). The space complexity is O(min(n, m)) where m is the size of the character set — at most 128 for ASCII or 26 for lowercase English letters.

This is the classic variable size sliding window pattern. The window grows when the constraint is satisfied (all unique characters) and shrinks when it is violated (a duplicate appears). The maximum window size seen during the traversal is your answer.

The Set-based solution is already O(n), but the inner while loop that shrinks left one position at a time can be improved. Instead of a Set, use a HashMap that stores each character mapped to its most recent index. When you encounter a duplicate, you can jump left directly to one past the previous occurrence.

With the HashMap approach, when s[right] already exists in the map and its stored index is >= left, you set left = map.get(s[right]) + 1. This skips all the intermediate removals. Then update the map with the new index for s[right] and compute the window length.

In practice, both approaches run in O(n) time. The HashMap version has a slight constant-factor advantage because it avoids the shrink loop entirely. More importantly, the code is cleaner — a single pass with no inner while loop. This is the version most interviewers expect to see.

The HashMap technique generalizes well. Whenever you need to track the last position of an element in a sliding window problem, a HashMap gives you direct index access. This same idea appears in problems like Minimum Window Substring (#76) and Longest Repeating Character Replacement (#424).

Empty string is the most common edge case — return 0 immediately. Both the Set and HashMap approaches handle this naturally since the loop never executes, but it is worth mentioning in an interview to show thoroughness.

A string with all identical characters like "aaaaa" should return 1. Your sliding window will expand right by one, detect a duplicate, and shrink left to match. The maximum window size never exceeds 1. This tests that your shrink logic works correctly.

A string with all unique characters like "abcdef" should return the full length. The window expands from start to finish without ever shrinking. This tests that your solution does not accidentally shrink when it should not.

Single character strings return 1. Strings with spaces, digits, and special characters work identically since the character set sliding window treats all characters uniformly. Always clarify the character set with your interviewer — ASCII vs Unicode can affect space complexity analysis.

LeetCode #3 is the gateway problem for the variable-size sliding window pattern. Unlike fixed-size windows where you slide a window of constant width, variable-size windows grow and shrink based on a constraint. The constraint for this problem is character uniqueness, but the same structure applies to many other problems.

Minimum Window Substring (#76) uses the same expand-right, shrink-left structure but tracks character frequencies instead of uniqueness. Longest Repeating Character Replacement (#424) allows K replacements while maintaining the window. Permutation in String (#567) checks if any window matches a target frequency map. The pattern is identical — only the constraint changes.

When you see a substring or subarray problem with a constraint that can be checked incrementally, think sliding window. If the window can vary in size, you need two pointers. If duplicates or frequencies matter, add a Set or HashMap. This mental framework covers a huge portion of medium-difficulty interview problems.

Practice this problem until the sliding window code flows without hesitation. Then apply the same template to #76, #424, and #567. YeetCode flashcards group these problems by pattern so you can drill the variable size sliding window family in a single session and build the muscle memory that makes interviews feel routine.