Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 104s consists of English letters, digits, symbols and spaces.Problem Overview: Given a string s, return the length of the longest substring that contains no repeated characters. The substring must be contiguous, so you cannot reorder characters or skip positions.
Approach 1: Brute Force Enumeration (O(n^3) time, O(min(n, charset)) space)
Check every possible substring and verify whether it contains duplicate characters. Two nested loops choose the start and end indices, and a third pass checks if the substring contains unique characters using a set. This works because you explicitly test every candidate substring, but the repeated scanning makes it extremely slow for large inputs. The approach demonstrates the core constraint—no repeated characters—but it does not scale.
Approach 2: Sliding Window with Set (O(n) time, O(min(n, charset)) space)
Use the sliding window technique with two pointers. Maintain a window [left, right] and store characters in a set. Move right forward while characters remain unique. If a duplicate appears, increment left and remove characters from the set until the duplicate disappears. Each character enters and leaves the window at most once, so the total number of operations stays linear. This pattern frequently appears in sliding window problems on strings.
Approach 3: Sliding Window with Hash Map (O(n) time, O(min(n, charset)) space)
Track the last seen index of each character using a hash map. When processing index right, check if the character was seen inside the current window. If so, jump left directly to lastSeen[char] + 1 instead of shrinking the window one step at a time. This avoids unnecessary removals and keeps the window valid with minimal updates. The algorithm relies on constant-time lookups from a hash table and processes each character once.
Recommended for interviews: Interviewers expect the optimized sliding window solution with a hash map. It runs in O(n) time and shows you understand two-pointer window expansion, duplicate detection, and constant-time lookups. Mentioning the brute force approach first helps demonstrate your reasoning process, but implementing the sliding window variant shows strong algorithmic skill.
This approach uses a two-pointer technique (often called a sliding window) to efficiently find the longest substring without repeating characters. The idea is to keep moving a start pointer to the right, while expanding the end pointer, ensuring all characters between the two pointers are unique.
The code uses an integer array index of size 128 to store the last index + 1 of each character. We iterate end over the string, and if the character has appeared before, we move the start pointer to the right of the previous index. Then, update the maxLen if the current substring length is greater than maxLen.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string. Each character is visited at most twice, once by the start pointer and once by the end pointer.
Space Complexity: O(1), since we use a fixed array of size 128 for ASCII characters.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Check | O(n^3) | O(min(n, charset)) | Conceptual baseline or explaining the constraint during interviews |
| Sliding Window with Set | O(n) | O(min(n, charset)) | General solution using two pointers and a set to maintain uniqueness |
| Sliding Window with Hash Map | O(n) | O(min(n, charset)) | Optimal interview solution with faster window jumps using last seen indices |
Longest Substring Without Repeating Characters - Leetcode 3 - Python • NeetCode • 657,669 views views
Watch 9 more video solutions →Practice Longest Substring Without Repeating Characters with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor