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, the sliding window’s start character is incremented by one, narrowing the window from the start, and that character is removed from our Set. Save max = (new result, previous max).

If the next character is already in our set, try a new window. 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.

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;
}