How to Find the Longest Substring Without Repeating Characters in JavaScript

Finding the longest substring without repeating characters is a common problem in programming. This problem can be approached with different algorithms, but one of the most efficient methods is the sliding window technique. This article will explain how to solve this problem using JavaScript.

Problem Definition

Given a string, you need to find the length of the longest substring that does not contain repeating characters. For example, for the input string 'abcabcbb', the longest substring without repeating characters is 'abc', which has a length of 3.

Approach

We'll use the sliding window technique with two pointers to keep track of the current substring. A set will help us track the characters in the current window. The basic idea is to expand the window by moving the right pointer and to contract it by moving the left pointer when a repeating character is found.

Algorithm

Initialize two pointers left and right to 0, and create a set charSet to store characters.
Expand the window by moving the right pointer and adding characters to charSet.
If a character is repeated (i.e., it is already in charSet), move the left pointer to shrink the window until the repeated character is removed.
Keep track of the maximum length of the window throughout the process.

JavaScript Implementation


function lengthOfLongestSubstring(s) {
  let left = 0;
  let right = 0;
  let maxLength = 0;
  const charSet = new Set();

  while (right < s.length) {
    if (!charSet.has(s[right])) {
      charSet.add(s[right]);
      maxLength = Math.max(maxLength, right - left + 1);
      right++;
    } else {
      charSet.delete(s[left]);
      left++;
    }
  }

  return maxLength;
}

// Example usage
const input = 'abcabcbb';
console.log(lengthOfLongestSubstring(input)); // Output: 3

In this implementation:

The while loop iterates through the string with the right pointer.
If the character at s[right] is not in charSet, it is added, and the length of the current window is checked for the maximum length.
If the character is already in charSet, the left pointer is moved to shrink the window until the repeating character is removed.
Finally, maxLength holds the length of the longest substring without repeating characters.

Conclusion

By using the sliding window technique, you can efficiently find the length of the longest substring without repeating characters in a given string. This approach ensures that you only traverse the string once, resulting in a time complexity of O(n). With this method, you can handle large inputs effectively and solve the problem with optimal performance.

Archive