Problem
Given a string, find the length of the longest substring without repeating characters.
Example
Input: "abcabcbb"
Output: 3
The answer is "abc".Solution
Sliding window with a hash map tracking the last index each character appeared. Move left edge past any duplicate.
def length_of_longest_substring(s):
last = {}
left = 0
max_len = 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1
last[ch] = right
max_len = max(max_len, right - left + 1)
return max_lenfunction lengthOfLongestSubstring(s) {
const last = new Map();
let left = 0, maxLen = 0;
for (let right = 0; right < s.length; right++) {
if (last.has(s[right]) && last.get(s[right]) >= left) {
left = last.get(s[right]) + 1;
}
last.set(s[right], right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}int lengthOfLongestSubstring(string s) {
unordered_map<char, int> last;
int left = 0, maxLen = 0;
for (int right = 0; right < s.size(); right++) {
if (last.count(s[right]) && last[s[right]] >= left) {
left = last[s[right]] + 1;
}
last[s[right]] = right;
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> last = new HashMap<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
if (last.containsKey(ch) && last.get(ch) >= left) {
left = last.get(ch) + 1;
}
last.put(ch, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}Complexity
- Time: O(n)
- Space: O(min(n, alphabet))
Explanation
The sliding window expands by moving right; when we hit a duplicate inside the window, we jump left past the previous occurrence.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?