003. Longest Substring Without Repeating Characters

At a Glance

• Topic: Hash Table
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 003

Problem Statement

Given a string s, find the length of the longest substring without duplicate characters.

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Note that "bca" and "cab" are also correct answers.

Example 2:

Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

Approach & Solution Steps

Use a sliding window with a Set to track characters in the current window. If a duplicate is found, remove characters from the left until the duplicate is gone. Keep track of the maximum window size.

Optimal JS Solution

function lengthOfLongestSubstring(s) {
  const set = new Set();
  let left = 0, max = 0;
  for (let right = 0; right < s.length; right++) {
    while (set.has(s[right])) {
      set.delete(s[left]);
      left++;
    }
    set.add(s[right]);
    max = Math.max(max, right - left + 1);
  }
  return max;
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.