LeetCode 3. Longest Substring Without Repeating Characters — Interactive JavaScript

Problem

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

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

Solution

Dynamic Programming Sliding Window with Set

Interactive Example using Promises

Explanation

Use a Sliding window. Go stepwise through characters of s to expand the longest unique string one character each step. Each time a new maximum size of characters in the Set is reached, it is stored in our variable, ans. The Set is used only to track the next possible longest unique set of characters.

If the next character in s is not in the Set, wordEnd is incremented, widening the window. Save ans = Max(new result, previous max).

If the next character is already in our Set, try a new window. We don’t know where in our word the next character exists, but we can try removing one char from the front of the set. This decreases the current running set of unique characters, but gives us a chance to possibly find a longer unique set.

MAX_LENGTH - wordStart > ans

If the length number of characters remaining are greater than our longest answer, continue the loop for a chance to get a longer answer.

Loop Terminal Condition

MAX_LENGTH - wordStart > ans

If the length number of characters remaining are greater than our longest answer, continue the loop (there is a chance to get a longer answer).

Time complexity

O(n)

Space complexity

O(2n)

JavaScript

function lengthOfLongestSubstring(s) {
    const MAX_LENGTH = s.length;
    const set = new Set();
    let ans = 0, wordStart = 0, wordEnd = 0;
    while (MAX_LENGTH - wordStart > ans) { // Loop terminal condition.
        if(!set.has(s[wordEnd])) {
            set.add(s[wordEnd++]);
            ans = Math.max(ans, wordEnd - wordStart);
        } else {
            set.delete(s[wordStart++]);
        }
    }
    return ans;
}

Changing while to do / while can improve performance. If the readability is good, why not use it?

Only one small tweak is needed to avoid an error. Can you spot the error?

function lengthOfLongestSubstring(s) {
    "use strict";
    const MAX_LENGTH = s.length;
    const testChars = new Set();

    let ans = 0, wordStart = 0, wordEnd = 0;
    if (MAX_LENGTH === 0) return 0;
    do { 
        if(!testChars.has(s[wordEnd])) {
            testChars.add(s[wordEnd++]);
            ans = Math.max(ans, wordEnd - wordStart);
        } else {
            testChars.delete(s[wordStart++]);
        }
    } while (ans < MAX_LENGTH - wordStart)
    return ans;
}

If s === "", its 0 property (wordEnd) is undefined.

We can avoid adding undefined to our map by doing a check for this special case before the loop.

if (MAX_LENGTH === 0) return 0;

Finally, adding "use strict" allows the script engine to make some of its own optimizations, more for sanity than performance. (This should mostly be done on the file level or by using modules or classes.) The result is readable and has phenomenal performance, beating 91.55 % of all javascript submissions.

Non-strict functions use a separate Environment Record for top-level lexical declarations. This is done so direct eval can determine whether any var-scoped declarations introduced by the eval code conflict with pre-existing top-level lexically scoped declarations. This is not needed for strict functions because strict direct eval places all declarations into a new Environment Record.