Longest Substring Without Repeating Characters
The key idea
Slide a window
[left, right] over s. As right advances, if the new character is already inside the window, jump left just past its previous occurrence so the window never holds a duplicate. The best window length seen is the answer.Problem
Given a string s, find the length of the longest substring without repeating characters.
A substring is a contiguous run of characters within s. The substring you return must contain no character more than once. If s is empty, the answer is 0.
Constraints
- 0 <= s.length <= 5 * 10^4
sconsists of English letters, digits, symbols and spaces.
Examples
Input: s = "abcabcbb"
Output: 3
Input: s = "bbbbb"
Output: 1
Input: s = "pwwkew"
Output: 3
Complexity
Time: O(n) Space: O(min(n, m))
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Sliding Window problems
- Find All Anagrams in a StringMEDIUM
- Longest Continuous Increasing SubsequenceEASY
- Longest Repeating Character ReplacementMEDIUM
- Longest Subarray of 1's After Deleting One ElementMEDIUM
- Max Consecutive Ones IIIMEDIUM
- Maximum Average Subarray IEASY
- Maximum Number of Vowels in a Substring of Given LengthMEDIUM
- Minimum Size Subarray SumMEDIUM
- Minimum Window SubstringHARD
- Permutation in StringMEDIUM
- Sliding Window MaximumHARD
- Substring with Concatenation of All WordsHARD