Longest Substring Without Repeating Characters
Last Updated: March 21, 2026
Understanding the Problem
We need to find the longest contiguous chunk of characters in s where no character appears more than once. The key word is "substring", which means the characters must be adjacent in the original string. A subsequence like "pwke" from "pwwkew" doesn't count because the characters aren't contiguous.
The core challenge is: how do we efficiently track which characters are in our current window and quickly detect when a duplicate enters? A naive approach would check every possible substring, but we can do much better by recognizing that when we find a duplicate, we don't need to start over from scratch. We just need to shrink the window until the duplicate is gone.
Key Constraints:
0 <= s.length <= 5 * 10^4→ With n up to 50,000, O(n^2) might pass but will be tight. O(n) is what we should aim for.- The string can contain letters, digits, symbols, and spaces. That's the full ASCII range (up to 128 unique characters), not just lowercase letters. This affects what data structures we choose for tracking characters.
- The string can be empty (
length = 0), so we need to handle that edge case.
Approach 1: Brute Force
Intuition
The most direct approach is to check every possible substring and see if it has all unique characters. For each starting index i, we try every ending index j >= i and verify that the substring s[i..j] contains no duplicates. We track the longest valid substring we find.
To check whether a substring has all unique characters, we can use a set. Add each character one by one. If we ever try to add a character that's already in the set, that substring has a duplicate.
Algorithm
- Initialize
maxLen = 0 - For each starting index
ifrom 0 to n-1: - Create a new set for this starting position
- For each ending index
jfromito n-1: - If
s[j]is already in the set, break (any longer substring starting atiwill also contain this duplicate) - Add
s[j]to the set - Update
maxLen = max(maxLen, j - i + 1) - Return
maxLen
Example Walkthrough
Code
- Time Complexity: O(n^2). We have two nested loops. The outer loop runs n times, and for each starting index, the inner loop can run up to n times. Each set operation is O(1), so the total is O(n^2).
- Space Complexity: O(min(n, m)). Where m is the size of the character set (128 for ASCII). The set stores at most min(n, m) characters.
The bottleneck is that when we find a duplicate, we throw away everything and start fresh from the next index. But most of the characters we already verified are still valid. What if instead of restarting, we just slid the left boundary forward to remove the duplicate and continued expanding to the right?
Approach 2: Sliding Window + Hash Set
Intuition
Instead of checking every substring independently, we maintain a window [left, right] that always contains unique characters. We expand the window by moving right forward. When s[right] is already in the window, we shrink the window by moving left forward and removing characters from our set until the duplicate is gone.
This is the classic sliding window pattern. Both pointers only move forward, so each character is added and removed from the set at most once. That gives us O(n) time.
Both left and right only move forward, never backward. Each character is added to the set exactly once (when right reaches it) and removed at most once (when left passes it). So even though there's a while loop inside the for loop, the total number of operations across the entire run is at most 2n, not n^2. This is the key insight that makes sliding window problems O(n).
Algorithm
- Initialize
left = 0,maxLen = 0, and an empty hash set - For each
rightfrom 0 to n-1: - While
s[right]is already in the set: - Remove
s[left]from the set - Increment
left - Add
s[right]to the set - Update
maxLen = max(maxLen, right - left + 1) - Return
maxLen
Example Walkthrough
Code
- Time Complexity: O(n). Each character is visited at most twice, once by
rightand once byleft. So the total work is O(2n) = O(n). - Space Complexity: O(min(n, m)). Where m is the character set size (128 for ASCII). The set holds at most min(n, m) characters.
This approach is already O(n), but there's a subtle inefficiency. When we hit a duplicate, we slide left forward one character at a time. What if we could jump left directly to the position right after the previous occurrence, skipping all those intermediate removals?
Approach 3: Sliding Window + Hash Map (Optimal)
Intuition
Instead of a set that only tells us whether a character is in the window, we use a hash map that stores the most recent index of each character. When we encounter a duplicate, we can jump the left pointer directly past the previous occurrence, no need to slide one step at a time.
The key detail: when we see that s[right] already exists in the map at index prevIndex, we set left = max(left, prevIndex + 1). The max is important because left might already be past prevIndex (if we jumped past it due to an earlier duplicate). Without the max, we'd move left backward, which would break the algorithm.
The hash map approach works because we never need to look at a character more than once. Each character gets its index recorded, and when we see it again, we know exactly where to move the left boundary. The max(left, prevIndex + 1) check ensures we never move left backward, which preserves the invariant that everything in [left, right] is unique.
Compared to the hash set approach, we avoid the inner while loop entirely. The left pointer might jump multiple positions in one step, but it still only moves forward. The total work across all iterations remains O(n), but with a smaller constant factor since we're not doing incremental removals.
Algorithm
- Initialize
left = 0,maxLen = 0, and an empty hash map (character to index) - For each
rightfrom 0 to n-1: - If
s[right]exists in the map and its stored index is>= left: - Move
lefttomap[s[right]] + 1(jump past the previous occurrence) - Update the map:
map[s[right]] = right - Update
maxLen = max(maxLen, right - left + 1) - Return
maxLen
Example Walkthrough
Code
- Time Complexity: O(n). Single pass through the string. Each character is processed exactly once by the
rightpointer. Theleftpointer jumps forward but never backward, so total movement is at most n. - Space Complexity: O(min(n, m)). Where m is the character set size (128 for ASCII). The map stores at most min(n, m) entries.