Javascript | Longest Substring Without Repeating Characters | O(n)

Given a string s, find the length of the longest substring without repeating characters.

Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

First you should learn about map and how we get /set the key — value pair. Lets look into map,

Map is a collection of keyed data items, just like an Object. But the main difference is that Map allows keys of any type.

Methods and properties are:

• new Map() – creates the map.
• map.set(key, value) – stores the value by the key.
• map.get(key) – returns the value by the key, undefined if key doesn’t exist in map.

let map = new Map();
map.set('1', 'str1');   // a string key
map.set(1, 'num1');     // a numeric key
map.set(true, 'bool1'); // a boolean key
// remember the regular Object? it would convert keys to string
// Map keeps the type, so these two are different:
alert( map.get(1)   ); // 'num1'
alert( map.get('1') ); // 'str1'
alert( map.size ); // 3

Lets look into the implementation, returns the maxLength of the Longest Substring Without Repeating Characters -

Example = “ababcd”

• when i = 0, start=0, ch = s[i] = a, “a” does not exist in the map, so it will add in the map using map.set(“a”, 0), maxLength (i-start+1) = (0–0+1) = 1.
• when i = 1, start = 0, ch = s[i] = b, “b” does not exist in the map, so it will add in the map using map.set(“b”, 1), then the maxLength = (i-start+1) = (1–0+1) = 2.
• when i = 2, ch = s[i] = a, now “a” exist in the map and greater than and equalTo start, it will calculate the start = (map.get(“a”) + 1) = 0 + 1 = 1. and set the map(“a”, 2), then the maxLength = (i — start + 1) = (2–1+1) = 2, maxLength is still 2 only.
• when i = 3, start =1 , ch = s[i] = b, now again “b” exist in the map and greater than start, it calculated the start = (map.get(“b”) + 1) = 1+ 1 = 2. and set the map(“b”, 3), then the maxLength = (i — start + 1 )= (3–2+1) = 2!> maxLength, maxLength is still 2 only.
• when i = 4, start=2, ch = s[i] = c, now again “c” does not exist in the map so it will add “c” in the map and set the map(“c”, 4), then the maxLength = (i — start + 1) = (4–2+1) = 3, and 3 > maxLength(2), so it will calculate the maxLength to 3.
• when i =5, ch = s[i] = d, now again “d” does not exist in the map so it will “d” in the map and set the map(“d”, 5), then the maxLength = (5–2+1) = 4, and 4> maxLength(3)
• finally, it will return the maxLength 4.

var lengthOfLongestSubstring = function(s) {
  var start = 0, maxLen = 0;
  var map = new Map();
for(var i = 0; i < s.length; i++) {
      var ch = s[i];
    
      if(map.get(ch) >= start) start = map.get(ch) + 1;
      map.set(ch, i);
    
      if(i - start + 1 > maxLen) maxLen = i - start + 1;
   }
return maxLen;
};

Thanks for reading the post.