Longest Substring Without Repeating Characters
Understanding the Problem
We need to find the longest contiguous run of characters in s where no character appears more than once. A substring requires the characters to be adjacent in the original string. A subsequence like "pwke" from "pwwkew" does not count because the characters are not contiguous.
The challenge is tracking which characters are in the current window and detecting when a duplicate enters. Checking every possible substring works, but it repeats effort. When a duplicate appears, the prefix we already validated is still valid, so instead of restarting we can shrink the window from the left 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
Check every possible substring and see whether it has all unique characters. For each starting index i, try every ending index j >= i and verify that the substring s[i..j] contains no duplicates. Track the longest valid substring found.
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 a duplicate appears, this approach discards the whole window and restarts from the next index, even though most of those characters are still valid. The next approach keeps a single window and slides its left boundary forward to drop the duplicate instead of restarting.
Approach 2: Sliding Window + Hash Set
Intuition
Maintain a window [left, right] that always contains unique characters. Expand it by moving right forward. When s[right] is already in the window, move left forward and remove characters from the set until the duplicate is gone, then add s[right].
A hash set holds the characters currently in the window, so the duplicate check is O(1).
The inner while loop looks like it could make this O(n^2), but it cannot. Both left and right only move forward. Each character is added to the set once (when right reaches it) and removed at most once (when left passes it). Across the whole run, the two pointers advance a combined total of at most 2n positions, so the work is 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 O(n), but it still slides left forward one position at a time on a duplicate. The next approach records where each character last appeared, so left can jump directly past the previous occurrence in a single step.
Approach 3: Sliding Window + Hash Map (Optimal)
Intuition
Replace the set with a hash map that stores the most recent index of each character. On a duplicate, move the left pointer directly past the previous occurrence instead of sliding it one step at a time.
When s[right] already exists in the map at index prevIndex, set left = max(left, prevIndex + 1). The max matters because left may already be past prevIndex from an earlier jump. Without it, left could move backward and re-include a character that was already removed from the window. Concretely, in "abba": after processing the second b, left is at index 2; reaching the final a finds its previous index 0, and max(2, 0 + 1) keeps left at 2 rather than rewinding to 1.
Every entry in the map is the latest index of a character. When s[right] was last seen at prevIndex and that index is inside the current window, every position from left to prevIndex either is the duplicate or sits before it, so none of them can stay. Jumping left to prevIndex + 1 removes exactly the part of the window that conflicts, in one step, and preserves the invariant that [left, right] holds only unique characters. The right pointer still visits each index once, so the total work is O(n).
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.