Created
November 18, 2019 04:28
-
-
Save kirkdrichardson/ea166ae91383682415ea1b1e66c15347 to your computer and use it in GitHub Desktop.
JavaScript - Find the Longest Substring of Unique Characters in O(N) - Sliding Window Pattern
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Write a function called longestSubstring, which accepts a string and returns the | |
| * length of the longest substring with all distinct characters. | |
| * | |
| * O(N) | |
| * | |
| */ | |
| function longestSubstring(str) { | |
| let longest = 0; | |
| let p1 = 0; | |
| let p2 = 0; | |
| const charIndices = {}; | |
| while (p2 < str.length) { | |
| let currChar = str[p2]; | |
| if (typeof charIndices[currChar] === 'number' && charIndices[currChar] >= p1) { | |
| // "Jump" p1 to location of the duplicate character to put it on the "edge" of the window. | |
| p1 = charIndices[currChar] + 1; | |
| // Reassign the mapped index of the (once again unique) character to the current value of our leading pointer, p2. | |
| charIndices[currChar] = p2; | |
| } else { | |
| charIndices[currChar] = p2; | |
| } | |
| p2++; // We continually move our leading pointer forward. | |
| // Determine length of current substring & update max if applicable. | |
| longest = Math.max(longest, p2-p1); | |
| } | |
| return longest; | |
| } | |
| console.log( | |
| longestSubstring('') === 0, | |
| longestSubstring('abb') === 2, | |
| longestSubstring('abcdefgaxxz') === 8, | |
| longestSubstring('helloworld') === 5, | |
| longestSubstring('testingandtesting') === 7, | |
| longestSubstring('aaaaaa') === 1, | |
| ); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment