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.
1const lengthOfLongestSubstring = function(s) {
2 const charIndex = new Map();
3 let maxLen = 0, start = 0;
4 for (let end = 0; end < s.length; end++) {
5 if (charIndex.has(s[end])) {
6 start = Math.max(start, charIndex.get(s[end]) + 1);
7 }
8 charIndex.set(s[end], end);
9 maxLen = Math.max(maxLen, end - start + 1);
10 }
11 return maxLen;
12};
13
14console.log(lengthOfLongestSubstring("abcabcbb")); // Output: 3
15console.log(lengthOfLongestSubstring("bbbbb")); // Output: 1
16console.log(lengthOfLongestSubstring("pwwkew")); // Output: 3
17The JavaScript solution includes using a Map to link characters to their most recent index position. As we iterate, we adjust the window start with any duplicates to maintain substrings of unique characters.