DEV Community

Duncan McArdle
Duncan McArdle

Posted on

1

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

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

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

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

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%

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.

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs