DSA AnimatorDSA animations
Longest Substring Without Repeating Characters LC #3 Medium Sliding Window · HashSet
Problem

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

Example 1
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with length 3.
Example 2
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with length 3. Note that "pwke" is a subsequence, not a substring.
Constraints: 0 ≤ s.length ≤ 5×10⁴ | s consists of English letters, digits, symbols, and spaces
Try Examples
Custom:
Approach
Variable sliding window [l..r] + HashSet — expand r, shrink l on duplicate
Move r right. If s[r] is already in the window, remove s[l] and advance l until unique again. Each character enters and leaves the set at most once → O(n) time.
String Window
l (left)
r (right)
in window
duplicate
best window
HashSet (window chars)
{ empty }
maxLen
0
Ready
Press ▶ Play or Next Step to begin.
Variables
l
0
r
—
winLen
—
maxLen
0
set
∅
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Init empty Set, l = 0, maxLen = 0
2
For each r from 0 to n−1: expand window right
3
While set.contains(s[r]): remove s[l], l++ (shrink left)
4
Add s[r] to set; maxLen = max(maxLen, r − l + 1)
5
Return maxLen after scanning all positions
Time
O(n)
Space
O(min(n, α))
Why This Works

A variable sliding window always holds a valid substring (no repeats). When s[r] duplicates a char already in the window, we shrink from the left until the duplicate is gone — the smallest valid window ending at r.

The HashSet gives O(1) membership checks. Each index enters and leaves the window at most once, so total work is O(n) despite the inner while loop.

maxLen tracks the best window seen so far. After each valid expansion at r, window length r − l + 1 is a candidate answer.

How to solve Longest Substring Without Repeating Characters

LeetCode 3 · Medium · Strings · Pattern: Sliding Window

Why the obvious approach is slow

Checking every substring is O(n) cubed. Even a smarter check is still O(n²). That is too slow for long strings.

The key idea

Keep a sliding window, from left to right. Right moves forward one character at a time. A hash map remembers the last index of every character. If the new character already appears inside the window, jump left to just after its previous index. At each step, update the best with the window length.

Remember

A window plus a last-seen map lets left jump, never step back. Only jump when the repeat is inside the current window.

Run the animation above on your own input, or watch the 1:51 video explanation of Longest Substring Without Repeating Characters with a dry run and Java code.

More Strings problems