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.
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.
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.
Solution #3: Map
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:
Solution #4: Set
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:
Comparing the solutions
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.
Top comments (0)