Longest Substring Without Repeating Characters
MediumVariable window · jump the left edge past repeats
Grow a window of letters with no repeats; when a repeat sneaks in, move the left edge past it.
The idea
Grow the window to the right. When a character repeats inside the window, jump the left edge to just past its previous position. The largest window seen is the answer.
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.