DSA problem
Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring that contains no repeating characters. A substring is a contiguous sequence of characters within the string, so the answer must be measured over a continuous run rather than an arbitrary selection of characters.
This is the canonical introduction to the variable-size sliding window. A brute-force approach would examine every possible substring and check each one for duplicates, which costs O(n^2) substrings times O(n) validation, an unacceptable O(n^3) overall. We need a way to extend and shrink a candidate window in amortized linear time.
The key observation is that the set of characters inside a valid window is always unique. As we push the right boundary forward to absorb a new character, the window may become invalid because that character already exists inside it. When that happens we advance the left boundary just far enough to evict the earlier copy, restoring the no-repeat invariant.
The intuition for the sliding window here is that the left pointer never moves backward. Every character is added once when the right pointer passes it and removed at most once when the left pointer passes it, so the total work is O(n). We track the best window length encountered while maintaining a hash set (or last-seen index map) of the characters currently inside the window.
Examples
s = "abcabcbb"3s = "bbbbb"1s = "pwwkew"3Constraints
- 0 <= s.length <= 5 * 10^4
- s consists of English letters, digits, symbols and spaces.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.