Longest Substring Without Repeating Characters in JavaScript

The "Longest Substring Without Repeating Characters" problem is a popular coding challenge that involves finding the length of the longest substring in a given string that contains no repeating characters. It falls under the category of string manipulation and sliding window algorithms.

This is a classic coding interview question that tests your understanding of string manipulation, hashing, and sliding window algorithms. It can be solved efficiently in O(N) time complexity, where N is the length of the input string s.

The Problem

Given a string s, our task is to find the length of the longest substring within s that contains no repeating characters.

For example, with an input of abcabcbb, the expected output would be 3.

This is because the longest substring without repeating characters is abc, which has a length of 3.

Approach

This is a classic Sliding Window Problem, to solve it we need to maintain a window (substring) with no repeating characters and keep track of its maximum length as we traverse the input string s.

To achieve this, we can use two pointers, (start and end), to represent the current window. We initialise both pointers at the beginning of the string and as we iterate through the string we move the end pointer to the right, expanding the window.

If we encounter a repeating character, we move the start pointer to the right until the repeating character is no longer part of the window. We update the maximum length of the window during this process.

This isn't dissimilar to the Two Pointer solution you would use when solving the 3Sum Problem or the Valid Palindrome Problem, although it is more complex.

The Solution in JavaScript

Using JavaScript (and TypeScript), the solution would look like this:

const lengthOfLongestSubstring = (s: string): number => {  const charIndexMap: Map<string, number> = new Map();  let maxLength = 0;  let start = 0;  for (let end = 0; end < s.length; end++) {    const currentChar = s[end];    if (      charIndexMap.has(currentChar) &&      charIndexMap.get(currentChar)! >= start    ) {      start = charIndexMap.get(currentChar)! + 1;    }    charIndexMap.set(currentChar, end);    const currentLength = end - start + 1;    maxLength = Math.max(maxLength, currentLength);  }  return maxLength;};

Here's an overview of how it works:

1. We define a function lengthOfLongestSubstring which takes a string s as input and returns the length of the longest substring without repeating characters.
2. We create a Map called charIndexMap, which will use to store the index of the most recent occurrence of each character in the string.
3. We then initialise variables maxLength and start to keep track of the maximum length and the starting index of the current window, respectively.
4. Using a loop, we iterate through the input string s using the end pointer as the loop variable. The end pointer represents the end of the current window.
5. Inside the loop, we retrieve the character at the current end index and check if it exists in the charIndexMap and if its index is greater than or equal to start. If so, this means that the character is repeating within the current window, and we need to move the start pointer to the right to exclude the repeating character from the window.
6. We then update the index of the current character in the charIndexMap to the current end index, representing the most recent occurrence of that character.
7. We calculate the current length of the window (substring) using the formula end ‑ start + 1.
8. We update the maxLength with the maximum of the current length and the previous maximum length encountered so far.
9. After the loop, we return maxLength, which represents the length of the longest substring without repeating characters.

Expanding the Solution: Returning the Matched Substring

Although it isn't asked for, it would also be fairly straightforward to expand upon this solution to also return the matched string, rather than just its length. Rather than storing and updating the string itself during the loop, we could simply keep track of the start and end indices of the longest substring during each iteration.

Then, we can use these indices to extract the substring from the original input string before returning it:

const longestSubstring = (s: string): { length: number; substring: string } => {  const charIndexMap: Map<string, number> = new Map();  let maxLength = 0;  let start = 0;  let longestSubstringStart = 0;  for (let end = 0; end < s.length; end++) {    const currentChar = s[end];    if (      charIndexMap.has(currentChar) &&      charIndexMap.get(currentChar)! >= start    ) {      start = charIndexMap.get(currentChar)! + 1;    }    charIndexMap.set(currentChar, end);    const currentLength = end - start + 1;    if (currentLength > maxLength) {      maxLength = currentLength;      longestSubstringStart = start;    }  }  const longestSubstring = s.substring(    longestSubstringStart,    longestSubstringStart + maxLength  );  return { length: maxLength, substring: longestSubstring };};

In this updated function, we added a new variable longestSubstringStart to keep track of the starting index of the longest substring found so far. Whenever we update the maxLength during the loop, we also update longestSubstringStart accordingly, essentially adding a second sliding window.

Finally, after the loop, we use the substring() method on the input string s to extract the characters of the longest substring using the longestSubstringStart and maxLength variables.

I've updated the return too, we now return an object containing both the length and the substring. Now, when you call longestSubstring(s), it will return an object with properties length and substring, where length is the length of the longest substring without repeating characters, and substring is the actual matched substring.

The Wrap‑Up

As with many of these leetcode‑type exercises, there is real‑world use in the methods you discover and develop to solve them. Here, we've employed the Sliding Window Technique and used a Map to keep track of the most recent occurrences of characters. This allows us to efficiently find the length of the longest substring without repeating characters in linear time complexity.