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.The key challenge in #3 Longest Substring Without Repeating Characters is efficiently tracking characters in a substring while ensuring none repeat. A brute-force approach would check every possible substring, but this leads to unnecessary repeated work and poor performance.
A more optimal strategy uses the Sliding Window technique combined with a Hash Table (such as a set or map). Maintain two pointers that represent the current window of characters. As you expand the window, track characters using a hash-based structure. If a duplicate character appears, move the left pointer forward until the substring becomes valid again.
This method ensures each character is processed at most twice, leading to an efficient O(n) time complexity. The extra space depends on the character set being stored in the hash structure, typically O(min(n, charset)). This pattern is common in substring and window-based interview problems.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window with Hash Table | O(n) | O(min(n, charset)) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Generate all possible substrings & check for each substring if it's valid and keep updating maxLen accordingly.
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.
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.
1#include <stdio.h>
2#include <string.h>
3
4int lengthOfLongestSubstring(char * s){
5 int n = strlen(s
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The sliding window technique helps avoid recomputing substrings from scratch. By adjusting window boundaries dynamically and tracking characters with a hash table, you can efficiently maintain a valid substring while scanning the string once.
Yes, this problem is commonly asked in FAANG and other top tech company interviews. It tests understanding of sliding window patterns, hash tables, and string manipulation, which are important interview fundamentals.
A hash-based data structure such as a HashSet or HashMap works best. It allows constant-time checks for whether a character already exists in the current substring window, which is essential for maintaining efficiency.
The optimal approach uses the sliding window technique with a hash table to track characters currently in the window. Two pointers expand and shrink the window while ensuring no duplicate characters remain. This allows the problem to be solved in linear time.