06. Longest Substring Without Repeating Characters

Difficulty:MediumPattern:Sliding WindowTime:O(n)Space:O(k)

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

How It Works & Algorithmic Design

Solves using the Variable Sliding Window with Hash Map Indexing:

Pointers: Maintain a sliding window defined by left boundary left and right boundary right.
Map Index Tracking: Use a Hash Map charIndexMap to store the last seen index of each character.
Expansion & Contraction: Expand right across string s:
- If character s[right] was seen inside the current window (charIndexMap[s[right]] >= left), update left = charIndexMap[s[right]] + 1 to skip past the repeating character.
- Update charIndexMap[s[right]] = right.
- Calculate window size (right - left + 1) and update maxLength.

Why This Approach Works Best

Instead of resetting the window or using nested loops ($O(n^2)$), jumping left directly past previous duplicate positions ensures each character is processed efficiently in $O(n)$ time and $O(k)$ space.

Example Walkthrough

Input: s = "abcabcbb"

Target string.

Window Execution: "abc" (len=3) -> 'a' repeats at idx 3 -> move left to idx 1 ("bca") -> len=3

Sliding window dynamically adjusts left edge.

Output: 3

Longest unique substring is "abc".

Answer: Sliding window unique substring search

function lengthOfLongestSubstring(s) {
  const map = new Map();
  let left = 0, maxLength = 0;
  for (let right = 0; right < s.length; right++) {
    if (map.has(s[right]) && map.get(s[right]) >= left) {
      left = map.get(s[right]) + 1;
    }
    map.set(s[right], right);
    maxLength = Math.max(maxLength, right - left + 1);
  }
  return maxLength;
}

💡 Dynamically adjust window boundary using character index mapping.

Key Takeaways

Store character indices to jump left pointer instantly.
Ensure the recorded index is $\ge left$ to avoid moving backwards.
Linear time complexity $O(n)$ with $O(k)$ space for distinct characters.