Q15: Longest Substring Without Repeating Characters
Find the length of the longest substring without repeating characters using the Sliding Window pattern.
Sliding Window Substring Search
function lengthOfLongestSubstring(s) {
const seen = new Set();
let left = 0;
let maxLength = 0;
for (let right = 0; right < s.length; right++) {
while (seen.has(s[right])) {
seen.delete(s[left]);
left++;
}
seen.add(s[right]);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
console.log(lengthOfLongestSubstring('abcabcbb')); // 3 ('abc')💡 Right pointer expands window. When duplicate character is detected, left pointer contracts window until duplicate is removed from set.
Key Takeaways
- Sliding window uses two pointers (
left,right) and a Set/Map. - Achieves O(n) linear time complexity.
Knowledge Check
What triggers the left window pointer to contract inward?