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 repeating characters. The substring must be continuous, so you cannot skip characters or reorder them.
Approach 1: Brute Force (O(n^3) time, O(min(n, k)) space)
Generate every possible substring and check if it contains duplicate characters. For each starting index i, extend the substring to j and verify uniqueness using a set or frequency array. The duplicate check itself scans the substring, which pushes the complexity to O(n^3). This approach is rarely used in production but helps you reason about the problem before introducing optimizations related to string processing.
Approach 2: Sliding Window with Hash Set (O(n) time, O(k) space)
Use the sliding window pattern with two pointers left and right. Expand the window by moving right while inserting characters into a set. If a duplicate appears, shrink the window by moving left and removing characters until the duplicate is removed. Each character is added and removed at most once, giving O(n) time. The set stores the current window's characters, so space complexity is O(k), where k is the character set size.
Approach 3: Optimized Sliding Window with Hash Map (O(n) time, O(min(n, k)) space)
This is the most common interview solution. Instead of shrinking the window one step at a time, store the last seen index of each character in a hash table. When you encounter a duplicate, jump the left pointer directly to lastIndex + 1. This avoids repeated removals and keeps the window valid in constant time. You still iterate through the string once, so the time complexity remains O(n), while the hash map stores at most one entry per character.
Recommended for interviews: Interviewers expect the optimized sliding window with a hash map. Starting with the brute force idea shows you understand the constraint of unique characters. Transitioning to the sliding window demonstrates algorithmic maturity and familiarity with common patterns used in string and two-pointer problems.
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.
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.
We can use two pointers l and r to maintain a sliding window that always satisfies the condition of having no repeating characters within the window. Initially, both l and r point to the first character of the string. We use a hash table or an array of length 128 called cnt to record the number of occurrences of each character, where cnt[c] represents the number of occurrences of character c.
Next, we move the right pointer r one step at a time. Each time we move it, we increment the value of cnt[s[r]] by 1, and then check if the value of cnt[s[r]] is greater than 1 within the current window [l, r]. If it is greater than 1, it means there are repeating characters within the current window, and we need to move the left pointer l until there are no repeating characters within the window. Then, we update the answer ans = max(ans, r - l + 1).
Finally, we return the answer ans.
The time complexity is O(n), where n is the length of the string. The space complexity is O(|\Sigma|), where \Sigma represents the character set, and the size of \Sigma is 128.
| Approach | Complexity |
|---|---|
| Sliding Window Approach | 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. |
| Sliding Window | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (check every substring) | O(n^3) | O(min(n, k)) | Conceptual understanding or very small inputs |
| Sliding Window with Hash Set | O(n) | O(k) | General solution using two pointers and window expansion/shrinking |
| Optimized Sliding Window with Hash Map | O(n) | O(min(n, k)) | Preferred interview approach with direct index jumps |
Longest Substring Without Repeating Characters - Leetcode 3 - Python • NeetCode • 817,350 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