Longest Substring Without Repeating Characters
MediumGiven a string s,
find the length of the longest substring without repeating characters.
A substring is a contiguous sequence of characters within the string. We need to find the longest such sequence where all characters are unique.
Example
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.
Explanation
The most efficient approach to solve this problem is using the sliding window technique with a hash map (dictionary) to track character positions.
The key insight is that we maintain a window of characters using two pointers (left and right). As we expand the window to include new characters, if we encounter a duplicate character that's already in our current window, we shrink the window from the left until the duplicate is removed.
The hash map stores the most recent index of each character. When we find a duplicate, we move the left pointer to max(left, last_seen[char] + 1). This ensures we never have duplicate characters in our window.
This approach works because:
- We only move the left pointer forward when we find a duplicate in our current window
- Each character is processed at most twice (once by right pointer, once by left pointer)
- The hash map gives us O(1) lookup for character positions
Idea Map
Initialize left = 0, char_map = {}, max_len = 0
For each right from 0 to n-1
If s[right] in char_map AND char_map[s[right]] >= left
→ left = char_map[s[right]] + 1
char_map[s[right]] = right
max_len = max(max_len, right - left + 1)
Complexity Analysis
Time Complexity
O(n) - We traverse the string once, and each character is processed at most twice (once by right pointer, once by left pointer). Hash map operations are O(1) on average.
Space Complexity
O(min(m, n)) - Where m is the size of the character set (ASCII: 128, Unicode: more). In the worst case, we store all unique characters in the string.
Code
def lengthOfLongestSubstring(s: str) -> int:
Initializes the function `lengthOfLongestSubstring` which takes a string `s` as input and returns the length of the longest substring without repeating characters.
char_map = {}
Creates an empty dictionary to store the most recent index of each character for O(1) lookups.
left = 0
Initializes the left pointer of our sliding window at position 0 (start of string).
max_len = 0
Initializes the variable to track the maximum length of valid substring found so far.
for right in range(len(s)):
Iterates through the string with `right` pointer expanding our window one character at a time.
if s[right] in char_map and char_map[s[right]] >= left:
Checks if current character exists in our map AND is within our current window (index >= left). This means we found a duplicate!
left = char_map[s[right]] + 1
Moves left pointer to one position after the previous occurrence of this character, removing the duplicate from our window.
char_map[s[right]] = right
Updates the map with the current character's most recent position (right pointer).
max_len = max(max_len, right - left + 1)
Calculates current window length (right - left + 1) and updates max_len if current window is longer.
return max_len
Returns the maximum length of substring without repeating characters found.
public int lengthOfLongestSubstring(String s) {
Initializes the function `lengthOfLongestSubstring` which takes a String `s` as input and returns the length of the longest substring without repeating characters.
Map<Character, Integer> charMap = new HashMap<>();
Creates a HashMap to store characters as keys and their most recent indices as values for O(1) lookups.
int left = 0;
Initializes the left pointer of our sliding window at position 0 (start of string).
int maxLen = 0;
Initializes the variable to track the maximum length of valid substring found so far.
for (int right = 0; right < s.length(); right++) {
Iterates through the string with `right` pointer expanding our window one character at a time.
char c = s.charAt(right);
Gets the current character at position `right`.
if (charMap.containsKey(c) && charMap.get(c) >= left) {
Checks if current character exists in our map AND its previous index is within our current window (index >= left). This means we found a duplicate!
left = charMap.get(c) + 1;
Moves left pointer to one position after the previous occurrence of this character, removing the duplicate from our window.
}
End of the if statement.
charMap.put(c, right);
Updates the map with the current character's most recent position (right pointer).
maxLen = Math.max(maxLen, right - left + 1);
Calculates current window length (right - left + 1) and updates maxLen if current window is longer.
}
End of the for loop.
return maxLen;
Returns the maximum length of substring without repeating characters found.
}
End of the function.
int lengthOfLongestSubstring(string s) {
Initializes the function `lengthOfLongestSubstring` which takes a string `s` as input and returns the length of the longest substring without repeating characters.
unordered_map<char, int> charMap;
Creates an unordered_map to store characters as keys and their most recent indices as values for O(1) lookups.
int left = 0;
Initializes the left pointer of our sliding window at position 0 (start of string).
int maxLen = 0;
Initializes the variable to track the maximum length of valid substring found so far.
for (int right = 0; right < s.length(); right++) {
Iterates through the string with `right` pointer expanding our window one character at a time.
char c = s[right];
Gets the current character at position `right`.
if (charMap.find(c) != charMap.end() && charMap[c] >= left) {
Checks if current character exists in our map AND its previous index is within our current window (index >= left). This means we found a duplicate!
left = charMap[c] + 1;
Moves left pointer to one position after the previous occurrence of this character, removing the duplicate from our window.
}
End of the if statement.
charMap[c] = right;
Updates the map with the current character's most recent position (right pointer).
maxLen = max(maxLen, right - left + 1);
Calculates current window length (right - left + 1) and updates maxLen if current window is longer.
}
End of the for loop.
return maxLen;
Returns the maximum length of substring without repeating characters found.
}
End of the function.
Edge Cases & Common Mistakes
Forgetting to check if duplicate is in current window
Always check char_map[s[right]] >= left before moving left pointer. A character might be in the map but outside our current window.
Empty string input
The algorithm handles empty strings correctly - the loop doesn't execute and returns 0.
All unique characters
When all characters are unique, the window keeps expanding and max_len becomes the length of the entire string.
Single character repeated
For strings like "aaaa", the window keeps resetting to size 1, correctly returning 1 as the answer.
Related Problems
What is the Sliding Window Technique?
The sliding window technique is a method for efficiently processing arrays/strings by maintaining a "window" of elements using two pointers. It's especially useful for problems involving subarrays or substrings with specific properties.
Learn more about sliding window →Disclaimer: This problem is for educational purposes. Practice the 'Longest Substring Without Repeating Characters' problem on LeetCode.