Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters

What is this problem about?

The Longest Substring Without Repeating Characters is a foundational computer science problem. Given a string s, you must find the length of the longest contiguous sequence of characters where no character appears more than once. For example, in the string "abcabcbb", the longest substring without repeating characters is "abc", which has a length of 3.

Why is this asked in interviews?

This problem is asked in nearly every tech company's interview loops (from startups to FAANG) because it is the ultimate test of the Sliding Window technique. It evaluates a candidate's ability to optimize a naive $O(N^3)$ or $O(N^2)$ brute-force check down to a highly efficient $O(N)$ linear scan. It effectively measures basic data structure knowledge, pointer manipulation, and edge-case handling.

Algorithmic pattern used

This is the textbook example of the Sliding Window and Hash Set / Hash Map pattern. You maintain a left and right pointer to represent the current window. As right iterates through the string, you add characters to a Hash Set. If the character at right is already in the set (a duplicate is found), you must shrink the window by moving the left pointer and removing characters from the set until the duplicate is eliminated.

Example explanation

String: "pwwkew"

• right=0 ('p'): Set {'p'}. Max = 1.
• right=1 ('w'): Set {'p', 'w'}. Max = 2.
• right=2 ('w'): Duplicate found! The set already has 'w'. We must move left.
  • left=0 ('p'): Remove 'p'. Set {'w'}. 'w' is still a duplicate!
  • left=1 ('w'): Remove 'w'. Set {}. Duplicate gone!
  • Add the new 'w'. Set {'w'}. Window is "w".
• right=3 ('k'): Set {'w', 'k'}. Max = 2.
• right=4 ('e'): Set {'w', 'k', 'e'}. Max = 3. ("wke")
• right=5 ('w'): Duplicate 'w'. Move left past the first 'w'. Window becomes "kew". Max remains 3.

Common mistakes candidates make

A very common mistake is clearing the entire Hash Set when a duplicate is found and resetting the left pointer to right. This discards valuable non-repeating characters! For example, in "dvdf", hitting the second 'd' shouldn't wipe out the 'v'. You must incrementally slide the left pointer, removing only the characters that fall outside the new window, until the specific duplicate is ejected.

Interview preparation tip

To master this interview pattern, learn the Hash Map optimization. Instead of using a Set and moving left step-by-step, use a Hash Map to store the index of each character. When you hit a duplicate, you can instantly jump the left pointer to map.get(char) + 1 (as long as that jump is forward!). This turns a $O(2N)$ algorithm into a strict $O(N)$ one-pass solution.