Longest Substring Without Repeating Characters medium
Description
Given a string s, find the length of the longest substring without repeating characters.
Examples
> Case 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
> Case 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
> Case 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that "pwke" is a subsequence, not a substring.Constraints
0 <= s.length <= 5 * 10^4sconsists of English letters, digits, symbols, and spaces
Approach 1: Brute Force
Check every possible substring for uniqueness.
Approach 2: Sliding Window with Set (Optimal)
Maintain a window [left, right] where all characters are unique. When a duplicate is found, shrink from the left.
Sliding window on "abcabcbb"
Step 1 of 8
a
[0]b
[1]c
[2]a
[3]b
[4]c
[5]b
[6]b
[7]right=0: Add 'a'. Window: {a}. Length=1. Max=1.
Approach 3: Sliding Window with HashMap (Even Better)
Instead of removing characters one by one, use a map to store the last index of each character. When a duplicate is found, jump left directly to the position after the previous occurrence.
Explanation
Set approach:
- Maintain a set of characters in the current window
- When adding a character that is already in the set, remove characters from the left until the duplicate is gone
- Track the maximum window size seen
HashMap approach:
- Instead of repeatedly removing from the left, store each character’s most recent index
- When encountering a duplicate, directly jump
leftto skip past the previous occurrence - This avoids the inner while loop, making each character processed in exactly O(1)
This is THE sliding window problem. If you can solve this, you understand the sliding window pattern well enough to tackle variants like “Minimum Window Substring” and “Longest Repeating Character Replacement.”
Analysis
Set approach:
- Time:
O(n)— each character is added/removed from set at most once - Space:
O(min(n, m))where m = character set size
HashMap approach:
- Time:
O(n)— single pass, no inner loop - Space:
O(min(n, m))where m = character set size