LeetCode 3 · Sliding Window · Hash Map

Longest Substring Without Repeating Characters

MediumSlide a window that never repeats a character and track its longest length.
Given a string s, find the length of the longest substring without repeating characters. A substring is a contiguous run of characters.

Walkthrough

try:
Slide a window [left, right] that never holds a repeated character; track its longest length.
0
1
2
3
4
5
6
7
a
b
c
a
b
c
b
b
·
·
·
·
·
·
·
·
seen(empty)
best = 0
windowright (new char)repeat foundbest window
1
function lengthOfLongestSubstring(s) {
2
  const seen = new Map();   // char -> last index
◄
3
  let left = 0;
4
  let best = 0;
5
  for (let right = 0; right < s.length; right++) {
6
    const c = s[right];
7
    if (seen.has(c) && seen.get(c) >= left) {
8
      left = seen.get(c) + 1;
9
    }
10
    seen.set(c, right);
11
    best = Math.max(best, right - left + 1);
12
  }
13
  return best;
14
}
seen = {}
step 0 / 40
line 2
Remember last positions
seen maps each character to the last index where we saw it. Empty to start.

Intuition

Keep a window [left, right] that always contains distinct characters. Move right forward one step at a time to grow it.

Remember the last index where you saw each character in a map. When the new character already sits inside the window, you must shrink from the left.

Instead of moving left one step at a time, jump it directly to one past the previous occurrence — that instantly removes the repeat.

After each step the window is valid again, so record its length and keep the best you have seen.

The algorithm

  1. 01Track left (window start), best length, and a map of each character’s last index.
  2. 02For each right, read c = s[right].
  3. 03If c was seen at an index ≥ left, move left to that index + 1.
  4. 04Record c’s new index, then update best with the current window length right − left + 1.
  5. 05Return best after scanning the whole string.

Reference implementation

1
function lengthOfLongestSubstring(s) {
2
  const seen = new Map();   // char -> last index
3
  let left = 0;
4
  let best = 0;
5
  for (let right = 0; right < s.length; right++) {
6
    const c = s[right];
7
    if (seen.has(c) && seen.get(c) >= left) {
8
      left = seen.get(c) + 1;     // jump past the previous occurrence
9
    }
10
    seen.set(c, right);
11
    best = Math.max(best, right - left + 1);
12
  }
13
  return best;
14
}

Complexity

Time
O(n) — right scans once and left only moves forward.
Space
O(min(n, alphabet)) for the last-seen map.