Longest Substring Without Repeating Characters in JS

Question

The task

is taken from leetcode

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

Example 1:

Input: "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"

Output: 3

Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

My solution

var lengthOfLongestSubstring = function(s) {
    const len = s.length;
    if (len < 2) { return len; }
    let res = [];
    let tmp = [];
    [...s].forEach(x => {
      if (tmp.includes(x)) {
        tmp = [...tmp.slice(tmp.findIndex(y => y === x ) + 1)];
      }
      tmp.push(x);    
      if (tmp.length > res.length) { res = tmp; }
    });
  return res.length;
};

Answer 1

Style

• Nice usage of arrow functions and spread operators. You can extend this to the function name as well:

  const lengthOfLongestSubstring = s => { ... };
  

• The code switches between two and four spaces within a block and between blocks. Choose one and stick with it throughout the entire program (the auto-formatter built into Stack Exchange does the job well).

• Avoid the intermediate variable len here:

      const len = s.length;
      if (len < 2) { return len; }
  

  The extra variable obfuscates the direct and explicit s.length and offers no performance benefit (as it would in C with strlen, which is linear). s.length is a numerical property and doesn't walk the list per call.

• Use vertical whitespace around blocks. Here's how I'd rewrite the above lines:

      ...
      if (s.length < 2) { 
        return s.length; 
      }
  
      let res = [];
      ...
  

  Then again, I prefer to omit this logic because the rest of the function body will handle the precondition automatically.

• Variable names can be a bit more specific: tmp => seen, x => char, res => longest.

Performance

Your solution runs in O(len(longest_subsequence) * n) time, which is in the 70th percentile of solutions for this problem. The culprits are includes, findIndex, slice and spread inside the for loop, all of which require visiting up to every element in tmp.

We can improve the time complexity to linear and reach the 99th percentile. The key is using an object as a hash map instead of an array to keep track of the history. For each character in s, add it to the object with a value of its latest-seen index. Keep track of the start of the current candidate run. Whenever we encounter an item already in the map, check to ensure its index is indeed inside the current run. If so, record a new longest (if applicable) and begin a new candidate run.

Here's the code:

const lengthOfLongestSubstring = s => {
  let longest = 0;
  let start = 0;
  const seen = {};

  [...s].forEach((char, i) => {
    if (char in seen && start <= seen[char]) {
      longest = Math.max(i - start, longest);
      start = seen[char] + 1;
    }

    seen[char] = i;
  });

  return Math.max(s.length - start, longest);
};

Answer 2

The answer by ggorlen covers most of the points and the alternative that was presented is very efficient, well sort of. In terms of complexity it is less complex and that shows when you compare your function.

If we use your algorithm and clean up some of the nasty bits, we get.

function longestSubstr(str) {
    var res = 0, tmp = [];
    for (const char of str){
        const idx = tmp.indexOf(char);
        if (idx > -1) { tmp = tmp.slice(idx + 1) }
        tmp.push(char);    
        if (tmp.length > res) { res = tmp.length }
    }
    return res;
}

Which makes it competitive up to about 160-180 characters, at which point using a hashing function beats the cost of stepping over each character.

If you consider a string 1Mb long your function does not stand a chance.

Beating the hashing function.

All the benefit of maps and sets come from the hash function. It takes an object (in this case a character) and turns it into a unique index that gives you the memory address of the data you are after.

In JavaScript the hash function must work for any type of data, not just strings and it is impressive at how well it does, but in this case, with 2 caveats, there is an even faster way.

The caveats:

• The string must be a ACSII string (8bits)

• We can hold some reserved memory to avoid allocation overhead.

It takes 256 array items to hold all the ASCII characters and we can create a unique hash directly from the ASCII character code.

The resulting function has the same complexity but by avoiding the JS hash calculation we get an order of magnitude better performance.

The following runs 10times faster than the existing answer. The algorithm (some slight mods) is ggorlen's so the credit is belongs to him

const longestASCIISubStr = (() => {
    const charLookup = new Uint32Array(256);
    return function (str) {
        var max = 0, start = 0, i = 0, char;
        charLookup.fill(0);
        const len = str.length;
        while (i < len)  {  
            const pos = charLookup[char = str.charCodeAt(i)];
            if (pos && start < pos) {
                max < i - start && (max = i - start);
                if (max > len - pos && i + max >= len) { return max }
                start = pos;
            }
            charLookup[char] = ++i;
        }
        return Math.max(len - start, max);
    }    
})();

I do not know the conditions of leetcode runtime environment so it may not work as allocating the lookup array is costly and will bring the average down for short strings.

The following does not require the reserved memory and is only about 5 times as fast for long string and equal at about 30 character strings but may be accepted as valid.

function longestASCIISubStr(str) {
    var max = 0, start = 0, i = 0, char;
    const charLookup = new Uint32Array(256);
    const len = str.length;
    while (i < len)  {  
        const pos = charLookup[char = str.charCodeAt(i)];
        if (pos && start < pos) {
            max < i - start && (max = i - start);
            if (max > len - pos && i + max >= len) { return max }
            start = pos;
        }
        charLookup[char] = ++i;
    }
    return Math.max(len - start, max);
}   

The problem with the less complex solution is that it comes with considerable overhead. The hashing function is complex compared to searching a dozen characters.