Watch 10 video solutions for Longest Substring Without Repeating Characters, a medium level problem involving Hash Table, String, Sliding Window. This walkthrough by NeetCode has 657,669 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |