Part 2 · Problems · Sliding window
Longest Substring Without Repeating Characters
#3 · Medium · LeetCode
Return the length of the longest substring with no repeated character.
abcabcbb -> 3 (abc) bbbbb -> 1 pwwkew -> 3 (wke)
Ask before coding
- Substring means contiguous?
- Character set?
Hint
Keep a window with no repeats. When a repeat comes in, move the left edge past its last position.
Approach
Map each character to its last index. Window is start..i. If the current character was last seen inside the window, move start to just after it. Track the max window length.
Time O(n) Space O(k)
Watch it run
Solution (JavaScript, tested)
function lengthOfLongestSubstring(s) {
const lastSeen = new Map();
let start = 0,
best = 0;
for (let i = 0; i < s.length; i++) {
const prev = lastSeen.get(s[i]);
if (prev !== undefined && prev >= start) start = prev + 1; // jump past the repeat
lastSeen.set(s[i], i);
best = Math.max(best, i - start + 1);
}
return best;
}Traps
- Only jump start forward if the old index is >= start ('abba' breaks otherwise).
- Substring is not subsequence.
Say out loud: Sliding window. The right edge always grows, the left edge only moves forward, so each character is processed a constant number of times.