LeetCode problem #3 — Longest substring without repeating characters (JavaScript)
Tags: leetcode, javascript, algorithms, programming
Published: 2022-03-09 16:00:11

In [this LeetCode challenge](https://leetcode.com/problems/longest-substring-without-repeating-characters) we’re asked to find the length of the longest string of characters in a provided string that does not contain repeating characters. In other words, in the string `hello` the longest substring without repeating characters is `hel` (with a length of 3).

The main method for solving this problem is with a “moving window”, and all of the below approaches use some form of this.

Solution #1: Double-loop with a Set
-----------------------------------

This was my first and by far least sophisticated method. In it, we loop once through all characters in the provided string, and then for each one we loop through the remaining characters, adding each one into a Set until we find a repeating character. At that point, we check if its the longest string found so far, and store its length if so. This repeats until the end of the string until we have found our longest substring.

{% embed https://gist.github.com/DuncanMcArdle/1ca896f43a38239f9a51b2e81f034c05 %}

Solution #2: Array
------------------

This solution is similar to the above, but instead uses an array to store the running string, which has the benefit of being ordered, and having the `splice` and `indexOf` functionality that make this solution particularly easy on the eye and removes the need for the nested loop.

{% embed https://gist.github.com/DuncanMcArdle/4f11e4414730be175850e5af7a92cea9 %}

Solution #3: Map
----------------

LeetCode user [nilath posted this great solution](https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1979/Simple-Javascript-Code) using a Map, which I have adjusted to improve readability. It takes the moving window concept but utilises Maps for lightning-fast lookups. Interestingly, because a Map is a key-value pair, we’re able to use the letter as the key, and the position that it sits within the string as the value:

{% embed https://gist.github.com/DuncanMcArdle/ba55c34b63ab5f68e6448cce4de69fbd %}

Solution #4: Set
----------------

This solution was inspired by [jeantimex’s Java solution](https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1812/Share-my-Java-solution-using-HashSet), and builds upon the Map concept but simplifies things slightly to use a Set instead. This has the benefit of reducing code complexity, but arguably damages readability:

{% embed https://gist.github.com/DuncanMcArdle/9c78f7d4b03c9eb651d95b0189c8cc12 %}

Comparing the solutions
-----------------------

All approaches (excluding the double-loop) are of similar performance, and vary between tests enough to make them negligible:

{% embed https://gist.github.com/DuncanMcArdle/3ac8c05eadb909c7d9fb9fb3be7d169c %}

What is interesting however is that LeetCode’s processor is so optimised for array work that if you start all of these approaches by first converting the string to an array (using `string.split('')`), you’ll see performance gains across the board.