Find the Longest Unique Substring!

Leetcode January Challenge #2: Longest Substring Without Repeating Characters (Javascript)

Photo by Mike Tinnion on Unsplash

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 character char (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 of char is greater than or equal to start. If it is, then update start to the latest index of char 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 to map: char as key and its index as value.
• If maxLen is greater than the length of substring, update maxLen. Since we are not recording the substring, we can get its length by i — 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 walkthroughlengthOfLongestSubstring("pwwkew").
• char is “p”. Its latest index is undefined. So no need to update start. Update map { “p” => 0 }. Update maxLen to 1.
• char is “w”. Its latest index is undefined. So no need to update start. Update map { “p” => 0, “w” => 1 }. Update maxLen to 2.
• char is “w”. Its latest index is 1 which is greater than start which is 0. So update start to 2. Update map { “p” => 0, “w” => 2 }. No need to update maxLen.
• char is “k”. Its latest index is undefined. So no need to update start. Update map { “p” => 0, “w” => 2, “k” => 3 }. No need to update maxLen.
• char is “e”. Its latest index is undefined. So no need to update start. Update map { “p” => 0, “w” => 2, “k” => 3, “e” => 4 }. Update maxLen to 3.
• char is “w”. Its latest index is 2 which is equal to start which is 2. So update start to 3. Update map { “p” => 0, “w” => 5, “k” => 3, “e” => 4 }. No need to update maxLen.

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.