LeetCode problem #3 — Longest substring without repeating characters (JavaScript)

In this LeetCode challenge 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.

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.

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.

LeetCode user nilath posted this great solution 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:

This solution was inspired by jeantimex’s Java solution, 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:

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

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Duncan McArdle

Full-stack software developer from the UK, author of the Aftermath book series, full time tech-nerd.