DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

codingpineapple
codingpineapple

Posted on

Leetcode 3. Longest Substring Without Repeating Characters

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

Example 1:

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

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

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.

Example 4:

Input: s = ""
Output: 0

Solution

Time complexity : O(n)

var lengthOfLongestSubstring = function(s) {
    let start = 0;
    let output = 0;
    let map = {}
    // In each loop currentLetter gets saved in the map
    // with its index+1 as the value
    for(let end = 0; end < s.length; end++) {
        const currentLetter = s.charAt(end);
       // If we have encountered currentLetter before,
       // we move the start pointer to the value
       // of currentLetter in the map or 
       // keep the start pointer the same depending 
       // on which value is greater
        if (map[currentLetter]!==undefined) {
          // This prevents the start pointer from decreasing
          start = Math.max(map[currentLetter], start);
        }
        output = Math.max(output, end - start + 1);
        // Add 1 to the index to prevent the currentLetter
        // from being included in the window when
        // currentLetter is encountered again
        map[currentLetter]=end+1;
    }
    return output;
};

Top comments (0)

This post blew up on DEV in 2020:

js visualized

πŸš€βš™οΈ JavaScript Visualized: the JavaScript Engine

As JavaScript devs, we usually don't have to deal with compilers ourselves. However, it's definitely good to know the basics of the JavaScript engine and see how it handles our human-friendly JS code, and turns it into something machines understand! πŸ₯³

Happy coding!