Longest Substring Without Repeating Characters
Problem
Given a string s, return the length of the longest substring without repeating characters.
- 0 ≤ s.length ≤ 5 * 10⁴
- s consists of English letters, digits, symbols and spaces.
Example
s = "abcabcbb"3The longest substring without repeating characters is "abc", which has length 3. The algorithm uses a sliding window to track the current substring without duplicates. Starting with an empty window, it expands the right pointer to include new characters. When a duplicate character is encountered, the left pointer moves forward to exclude the previous occurrence, ensuring the substring remains unique. This dynamic adjustment maintains the longest valid substring seen so far.
Approach
Straightforward Solution
A brute-force approach would check every possible substring and verify if it contains duplicates, resulting in O(n^3) time complexity due to substring generation and duplicate checks. This is inefficient for large inputs.
Core Observation
A substring without repeating characters can be represented as a contiguous window in the string where all characters are unique. The problem reduces to finding the maximum length of such a window.
Path to Optimal
The key recognition signals are 'longest substring' (implying contiguous sequence) and 'without repeating characters' (implying uniqueness constraint). These indicate the Sliding Window pattern because it efficiently maintains a window of unique characters by expanding and contracting pointers. Using a hash map to track the last seen indices of characters allows quick detection of duplicates and adjustment of the window's left boundary, reducing the complexity to O(n).
Optimal Approach
Use two pointers, left and right, to represent the current window. Iterate right over the string, and for each character, if it has been seen before and its last seen index is within the current window, move left to one position after that index to exclude the duplicate. Update the character's last seen index in the map and track the maximum window size. This approach guarantees each character is visited at most twice, resulting in O(n) time complexity.
Time
O(n)
Each character is visited at most twice: once when the right pointer advances and once when the left pointer moves forward to remove duplicates. Hash map lookups and updates are O(1) on average.
Space
O(min(m, n))
The hash map stores the last seen index of characters currently in the window. In the worst case, the window contains all unique characters, so the space is proportional to the size of the character set or the string length, whichever is smaller.
Pattern Spotlight
Sliding Window (Dynamic Window Adjustment)
Maintain a window with unique elements by expanding the right pointer and moving the left pointer forward only when duplicates are detected, using a hash map to track last seen positions for constant-time duplicate detection and window adjustment.
Solution
| 1 | class Solution:
|
| 2 | def lengthOfLongestSubstring(self, s: str) -> int:
|
| 3 | char_index_map = {}
|
| 4 | left = 0
|
| 5 | max_length = 0
|
| 6 |
|
| 7 | for right in range(len(s)):
|
| 8 | char = s[right]
|
| 9 | if char in char_index_map:
|
| 10 | left = max(char_index_map[char] + 1, left)
|
| 11 |
|
| 12 | char_index_map[char] = right
|
| 13 | max_length = max(max_length, right - left + 1)
|
| 14 |
|
| 15 | return max_length |
| 1 | import java.util.HashMap; |
| 2 | import java.util.Map; |
| 3 | |
| 4 | class Solution { |
| 5 | public int lengthOfLongestSubstring(String s) { |
| 6 | Map<Character, Integer> charIndexMap = new HashMap<>(); |
| 7 | int left = 0; |
| 8 | int maxLength = 0; |
| 9 | |
| 10 | for (int right = 0; right < s.length(); right++) { |
| 11 | char ch = s.charAt(right); |
| 12 | if (charIndexMap.containsKey(ch)) { |
| 13 | left = Math.max(charIndexMap.get(ch) + 1, left); |
| 14 | } |
| 15 | |
| 16 | charIndexMap.put(ch, right); |
| 17 | maxLength = Math.max(maxLength, right - left + 1); |
| 18 | } |
| 19 | |
| 20 | return maxLength; |
| 21 | } |
| 22 | } |
| 1 | #include <string> |
| 2 | #include <unordered_map> |
| 3 | #include <algorithm> |
| 4 | |
| 5 | using namespace std; |
| 6 | |
| 7 | class Solution { |
| 8 | public: |
| 9 | int lengthOfLongestSubstring(string s) { |
| 10 | unordered_map<char, int> charIndexMap; |
| 11 | int left = 0; |
| 12 | int maxLength = 0; |
| 13 | |
| 14 | for (int right = 0; right < (int)s.size(); right++) { |
| 15 | char ch = s[right]; |
| 16 | if (charIndexMap.find(ch) != charIndexMap.end()) { |
| 17 | left = max(charIndexMap[ch] + 1, left); |
| 18 | } |
| 19 | |
| 20 | charIndexMap[ch] = right; |
| 21 | maxLength = max(maxLength, right - left + 1); |
| 22 | } |
| 23 | |
| 24 | return maxLength; |
| 25 | } |
| 26 | }; |
| 1 | var lengthOfLongestSubstring = function(s) { |
| 2 | const charIndexMap = new Map(); |
| 3 | let left = 0; |
| 4 | let maxLength = 0; |
| 5 | |
| 6 | for (let right = 0; right < s.length; right++) { |
| 7 | const ch = s[right]; |
| 8 | if (charIndexMap.has(ch)) { |
| 9 | left = Math.max(charIndexMap.get(ch) + 1, left); |
| 10 | } |
| 11 | |
| 12 | charIndexMap.set(ch, right); |
| 13 | maxLength = Math.max(maxLength, right - left + 1); |
| 14 | } |
| 15 | |
| 16 | return maxLength; |
| 17 | }; |
Step-by-Step Solution
Track Character Indices and Window Boundaries to Maintain Uniqueness
| 3 | char_index_map = {}
|
| 4 | left = 0
|
| 5 | max_length = 0
|
| 7 | for right in range(len(s)):
|
| 8 | char = s[right]
|
| 9 | if char in char_index_map:
|
| 10 | left = max(char_index_map[char] + 1, left)
|
| 12 | char_index_map[char] = right
|
Objective
To maintain a mapping of characters to their most recent indices and dynamically adjust the window's left boundary to exclude duplicates.
Key Insight
By storing the last seen index of each character, the algorithm can detect duplicates within the current window in constant time. When a duplicate is found, moving the left pointer to one position after the previous occurrence removes the duplicate from the window. Using max ensures the left pointer never moves backward, preserving the window's integrity. This dynamic adjustment maintains a valid substring without duplicates at all times.
Interview Quick-Check
Core Logic
Use a hash map to store the last seen index of each character and update the left pointer to exclude duplicates by moving it to max(previous index + 1, current left).
State & Boundaries
The window is defined by [left, right], and left only moves forward to maintain a valid substring without duplicates.
Common Pitfalls & Bugs
Failing to use max when updating left can cause the left pointer to move backward, invalidating the window and causing incorrect results.
Complexity
Each character is processed once by the right pointer and at most once by the left pointer, ensuring O(n) time complexity.
Update Maximum Length Based on Current Window Size
| 13 | max_length = max(max_length, right - left + 1)
|
Objective
To continuously track and update the length of the longest substring without repeating characters found so far.
Key Insight
After adjusting the window boundaries to ensure uniqueness, the current window size (right - left + 1) represents a valid substring length. Comparing and storing the maximum window size seen so far ensures the algorithm returns the correct longest substring length at the end. This incremental update avoids the need for separate passes or substring extraction.
Interview Quick-Check
Core Logic
Calculate the current window size as right - left + 1 and update max_length if this size is larger.
State & Boundaries
Update max_length inside the loop after adjusting left to ensure the window is valid.
Common Pitfalls & Bugs
Forgetting to update max_length in every iteration can lead to missing the longest substring.
Return the Length of the Longest Unique Substring
| 15 | return max_length |
Objective
To provide the final result representing the maximum length of a substring without repeating characters.
Key Insight
After processing the entire string with the sliding window, max_length holds the length of the longest valid substring found. Returning this value completes the solution, as it reflects the global maximum tracked during the iteration.
Interview Quick-Check
Core Logic
Return max_length after the loop completes to provide the final answer.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
left = max(char_index_map[char] + 1, left)Move the left pointer to exclude the previous occurrence of the duplicate character.
This line is the core of the sliding window adjustment; it prevents the left pointer from moving backward and guarantees the window always contains unique characters by skipping past the last duplicate's position.
if char in char_index_map:Check if the current character has been seen before in the window.
This conditional is the key to detecting duplicates within the current window, enabling the algorithm to maintain the uniqueness constraint by adjusting the left pointer.
max_length = max(max_length, right - left + 1)Update the maximum length found so far based on the current window size.
This line captures the global maximum substring length by comparing the current window size, which is essential for the correctness of the final result.
char_index_map = {}Initialize a hash map to store the last seen index of each character.
This data structure enables constant-time lookup of character positions, which is essential for detecting duplicates and adjusting the window efficiently.
char_index_map[char] = rightUpdate the last seen index of the current character to the right pointer's position.
Recording the latest index allows future duplicate detection and correct window adjustments as the right pointer advances.
left = 0Initialize the left pointer of the sliding window to 0.
The left pointer marks the start of the current substring window and moves forward to exclude duplicates, maintaining the window's validity.
return max_lengthReturn the maximum length of substring without repeating characters.
Returning max_length provides the final answer after the entire string has been processed with the sliding window technique.
max_length = 0Initialize the variable that records the maximum substring length found so far.
Tracking the best window length is required for producing the final answer and must start at zero.
for right in range(len(s)):Iterate over the string with the right pointer to expand the window.
The right pointer explores each character sequentially, expanding the window and enabling the detection of duplicates within the current substring.
char = s[right]Retrieve the current character at the right pointer.
Accessing the current character is necessary to check for duplicates and update the hash map accordingly.
Test Your Understanding
Why must the left pointer move to max(char_index_map[char] + 1, left) instead of simply char_index_map[char] + 1?
Because the left pointer can only move forward, never backward. Using max ensures that left does not move backward when the repeated character's last occurrence is before the current left boundary, preserving the window's validity.
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Longest Substring Without Repeating Characters from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Longest Substring Without Repeating Characters drill