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.

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.

	var lengthOfLongestSubstring = function (s) {
	// Initialise a set to store the longest string in
	let longestStringLength = 0;
	// Loop through the provided string
	for (let i = 0; i < s.length; i++) {
	// Initialise a set to store the string created from the current point
	let currentStringSet = new Set();
	// Loop through the letters from the current point
	for (let x = i; x < s.length; x++) {
	// Check if the current letter exists in the current Set
	if (currentStringSet.has(s[x])) {
	// Move on from the current letter without adding it (as it already exists in the set)
	break;
	} else {
	// Character not found, add it to the set
	currentStringSet.add(s[x]);
	}
	}
	// Update the longest string length (if this one was bigger)
	longestStringLength = Math.max(
	longestStringLength,
	currentStringSet.size
	);
	}
	return longestStringLength;
	};

view raw blog_leetcode_problem-3_double-loop.js hosted with ❤ by GitHub

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.

	var lengthOfLongestSubstring = function (s) {
	// Initialise an array to store the running characters and a longest string length variable
	let currentString = [];
	let longestStringLength = 0;
	// Loop through the provided string
	for (let i = 0; i < s.length; i++) {
	// Attempt to get the current character's position in the current string
	const currentCharacterPosition = currentString.indexOf(s[i]);
	// Check if the current character exists in the current string
	if (currentCharacterPosition !== -1) {
	// Chop the array off after the occurence of the character
	currentString.splice(0, currentCharacterPosition + 1);
	}
	// Add the current character to the array
	currentString.push(s[i]);
	// Store the current string length if bigger than the existing record
	longestStringLength = Math.max(
	longestStringLength,
	currentString.length
	);
	}
	return longestStringLength;
	};

view raw blog_leetcode_problem-3_array.js hosted with ❤ by GitHub

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:

	var lengthOfLongestSubstring = function (s) {
	// Store counters for the the start of the window and the longest string's length
	var startOfWindow = 0,
	longestStringLength = 0;
	// Initialise a Map to store the characters of the current string
	var characterMap = new Map();
	// Loop through the provided string
	for (let i = 0; i < s.length; i++) {
	// Store the current character, and its position in the Map (saves repeatedly looking it up)
	let currentCharacter = s[i];
	let currentCharacterPositionInMap = characterMap.get(currentCharacter);
	// Check if current character exists in the Map, and was found within the current window
	if (currentCharacterPositionInMap >= startOfWindow) {
	// Move the current window to start after the first instance of the current character
	startOfWindow = currentCharacterPositionInMap + 1;
	}
	// Add the current character to the Map with its position in the string
	characterMap.set(currentCharacter, i);
	// Store the current string length if bigger than the existing record
	longestStringLength = Math.max(
	longestStringLength,
	i - startOfWindow + 1
	);
	}
	return longestStringLength;
	};

view raw blog_leetcode_problem-3_map.js hosted with ❤ by GitHub

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:

	var lengthOfLongestSubstring = function (s) {
	// Store counters for the biggest string, the start of the window, and the current letter's position (end of window)
	let longestStringLength = 0,
	startOfWindow = 0,
	currentPosition = 0;
	// Initialise a Set to store the characters
	let characterSet = new Set();
	// Loop through the provided string
	while (currentPosition < s.length) {
	// Check if the current character exists in the Set
	if (characterSet.has(s[currentPosition])) {
	// If so, delete it from the Set (as it will be picked up on the next run), and move the window's start forwards
	characterSet.delete(s[startOfWindow++]);
	} else {
	// If not, add the current character to the Set, and move the current character forwards
	characterSet.add(s[currentPosition++]);
	longestStringLength = Math.max(
	longestStringLength,
	characterSet.size
	);
	}
	}
	return longestStringLength;
	};

view raw blog_leetcode_problem-3_set.js hosted with ❤ by GitHub

Comparing the solutions

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

	Approach	Time to execute	Faster than	Memory usage	Smaller than
	Double loop	300ms	26.29%	45.1MB	5.07%
	Array	100ms	92.30%	42MB	5.07%
	Map	108ms	78.89%	41MB	5.07%
	Set	104ms	86.41%	42.8MB	5.07%

view raw blog_leetcode_problem-3_performance-comparison.csv hosted with ❤ by GitHub

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.