AlgoViz
HomeSliding Window

Longest Substring Without Repeats

Medium

Jump the left edge past the previous copy

Problem

Return the length of the longest substring without repeating characters.

In simple words

Grow a window; when a repeat appears, jump the left edge past the earlier copy.

The idea

Store the last index at which each character appeared. When a repeat arrives, move the left edge to just after that previous occurrence rather than stepping it along one at a time, so the window is repaired in O(1).

The trick

  • Never move left backwards — take max(left, lastIndex + 1).
  • Record the length after each expansion, not only at the end.
  • O(n) time, O(alphabet) space.
a
b
c
a
b
c
b
b
0
1
2
3
4
5
6
7

Step 1 of 27. Brute force: from each start, extend until a letter repeats — starting over each time. Values: a, b, c, a, b, c, b, b.

1/27
Brute force
timeO(n²)spaceO(n)

Restart at each index.

1for (let i = 0; i < n; i++) {2  const seen = new Set();3  let j = i;4  while (j < n && !seen.has(s[j])) seen.add(s[j++]);5  best = Math.max(best, j - i);6}

Input

array
[a, b, c, a, b, c, b, b]

Memory

repeat
—

Output

best
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
s = "abcabcbb"
Output:
3
Explanation:
"abc" is the longest stretch with no repeat.

Example 2

Input:
s = "bbbbb"
Output:
1
Explanation:
Only "b" fits → length 1.

Example 3

Input:
s = "pwwkew"
Output:
3
Explanation:
"wke" gives length 3.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.