DSA Tracker

Visualize

Grow-and-shrink window

A repeat only forces the window to shrink, never to restart from scratch: when s[r] already lives in the window, evicting from the left until that clash clears is enough, because every character removed along the way would only re-trigger the same clash if it stayed. That's why both edges move forward only — r keeps probing new characters while l creeps right just enough to resolve a duplicate — so the window [l..r] never backtracks and each character is added and removed at most once. Reach for it when the answer is a contiguous run and validity can be checked incrementally, like "no repeated characters".

Details

Animated on: Longest substring without repeating characters in "abcabcbb"

Problem:Longest Substring Without Repeating CharactersMedium

Pattern:Sliding Window

Sliding Window

step 1 / 18

a
[0]
b
[1]
c
[2]
a
[3]
b
[4]
c
[5]
b
[6]
b
[7]

Input "abcabcbb". Window [l..r] may hold each char once; a Set remembers what's inside. Start l=0, best=0.

  • l=0· arr[0] = a
  • r=0· arr[0] = a
Pseudocode
1seen = an empty set of the characters in the window
2l = 0, best = 0
3FOR each right edge r from 0 to the end of s:
4  WHILE s[r] is already in seen:
5    remove s[l] from seen
6    move l one step right
7  END WHILE
8  add s[r] to seen
9  best = the larger of best and the window size (r - l + 1)
10END FOR
11RETURN best

← / → step · space play · Home restart

Every step in words

Show all 18 steps
  1. Input "abcabcbb". Window [l..r] may hold each char once; a Set remembers what's inside. Start l=0, best=0.
  2. 'a' isn't in the Set, so the window grows to include it. Window "a", length 1, best=1.
  3. 'b' is new too — extend right, no shrinking needed. Window "ab", best=2.
  4. 'c' is new — extend again. Window "abc", all unique, best=3.
  5. Second 'a' arrives but 'a' is already in the Set — the window can't legally grow. Must shrink from the left until the old 'a' leaves.
  6. Evict the old 'a' at index 0 and slide l to 1. 'a' is free again — the clash is cleared.
  7. Add the new 'a'. Window "bca" has length 3 — ties best=3, no improvement, but we never re-scanned anything.
  8. 'b' repeats (index 1 already holds one). Same rule: duplicates always leave from the left, never the right.
  9. Old 'b' evicted, l=2, new 'b' added. Window "cab", length 3 — best stays 3.
  10. 'c' repeats now. Shrink from the left until the clash clears — one eviction is enough here.
  11. Old 'c' out, l=3, new 'c' in. Window "abc" again, length 3 — best still 3.
  12. 'b' at index 6 clashes with the 'b' at index 4 — it sits mid-window, so shrinking will cost more than one cell this time.
  13. The while loop keeps evicting: 'a' goes, still clashing, then 'b' goes. l lands on 5 — innocent chars left of a dup must go too.
  14. Add the new 'b'. Window "cb", length 2 — shrinking cost us size, but best=3 is safely recorded.
  15. Another 'b' immediately — the duplicate is right next door at index 6. Shrink again.
  16. 'c' then 'b' evicted, l=7. Trailing repeats squeeze the window down to almost nothing — that's fine, best is already banked.
  17. Add 'b'. Window is just "b", length 1 — best stays 3. Every char entered and left the window at most once: O(n).
  18. Loop ends. Answer: longest substring without repeating characters has length 3 — "abc", first seen at indices 0..2.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Longest Substring Without Repeating Characters in the editorAll Sliding Window problemsBack to roadmap