Find the Longest Unique Substring!
Leetcode January Challenge #2: Longest Substring Without Repeating Characters (Javascript)
Prompt:
- A string
s
- Find the length of the longest substring without repeating characters
Examples:
ex 1)
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
ex 2)
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
My Solution:
- A
map
will record { current character => its latest index } (for example, { ‘a’ => 0, ‘b’ => 2 } for “abb”). start
is the start of the current substring.maxLen
is the maximum length of the substring.- Iterate through each character of
s
. Let’s call the current characterchar
(in other words,let char = s[i]
). - Since the substring should not contain repeated characters, the current substring should be updated whenever we encounter repeated characters. To check if
char
already appeared, see if the latest index ofchar
is greater than or equal tostart
. If it is, then updatestart
to the latest index ofchar
plus one. We should add one because we want the new substring to start right after the repeated character. - Then, we can update the latest index of
char
. Add an element tomap
:char
as key and its index as value. - If
maxLen
is greater than the length of substring, updatemaxLen
. Since we are not recording the substring, we can get its length byi — start + 1
.
function lengthOfLongestSubstring(s) {
var start = 0, maxLen = 0;
var map = new Map(); for (var i = 0; i < s.length; i++) {
let char = s[i]; if (map.get(char) >= start) {
start = map.get(char) + 1;
} map.set(char, i);
maxLen = Math.max(maxLen, i - start + 1);
} return maxLen;
};
Testing:
- Let’s walkthrough
lengthOfLongestSubstring("pwwkew")
. char
is “p”. Its latest index is undefined. So no need to updatestart
. Updatemap
{ “p” => 0 }. UpdatemaxLen
to 1.char
is “w”. Its latest index is undefined. So no need to updatestart
. Updatemap
{ “p” => 0, “w” => 1 }. UpdatemaxLen
to 2.char
is “w”. Its latest index is 1 which is greater thanstart
which is 0. So updatestart
to 2. Updatemap
{ “p” => 0, “w” => 2 }. No need to updatemaxLen
.char
is “k”. Its latest index is undefined. So no need to updatestart
. Updatemap
{ “p” => 0, “w” => 2, “k” => 3 }. No need to updatemaxLen
.char
is “e”. Its latest index is undefined. So no need to updatestart
. Updatemap
{ “p” => 0, “w” => 2, “k” => 3, “e” => 4 }. UpdatemaxLen
to 3.char
is “w”. Its latest index is 2 which is equal tostart
which is 2. So updatestart
to 3. Updatemap
{ “p” => 0, “w” => 5, “k” => 3, “e” => 4 }. No need to updatemaxLen
.
Reflection:
Difficulty : ★★★☆☆
Runtime : (my runtime beats 83.65% of javascript submissions)
Note : We used a map because updating and adding elements to the map takes constant time. Since we are iterating through the loop once, it takes O(n). To be specific, n is the length of s
.