DSAMotivator

Longest Substring Without Repeating Characters

Medium·🪟 Sliding Window·Open on LeetCode ↗

Find the length of the longest run of consecutive characters in a string that contains no character twice.

s = "abcabcdb"step 1/21
L↓
a
b
c
a
b
c
d
b
0
1
2
3
4
5
6
7

Grow a window that is always free of repeats. Only the newest character can break that.

1def length_of_longest_substring(s):
2    last = {}
3    best = 0
4    left = 0
5    for right, ch in enumerate(s):
6        if ch in last and last[ch] >= left:
7            left = last[ch] + 1
8        last[ch] = right
9        best = max(best, right - left + 1)
10    return best
Read the 21 steps as text
  1. 1Grow a window that is always free of repeats. Only the newest character can break that.
  2. 2Add 'a' at index 0.
  3. 3Window is "a" — 1 characters, a new best.
  4. 4Add 'b' at index 1.
  5. 5Window is "ab" — 2 characters, a new best.
  6. 6Add 'c' at index 2.
  7. 7Window is "abc" — 3 characters, a new best.
  8. 8Add 'a' at index 3.
  9. 9'a' is already in the window at index 0. Any window starting at or before 0 contains it twice — jump the left edge to 1.
  10. 10Window is 3 long. Best stays 3.
  11. 11Add 'b' at index 4.
  12. 12'b' is already in the window at index 1. Any window starting at or before 1 contains it twice — jump the left edge to 2.
  13. 13Window is 3 long. Best stays 3.
  14. 14Add 'c' at index 5.
  15. 15'c' is already in the window at index 2. Any window starting at or before 2 contains it twice — jump the left edge to 3.
  16. 16Window is 3 long. Best stays 3.
  17. 17Add 'd' at index 6.
  18. 18Window is "abcd" — 4 characters, a new best.
  19. 19Add 'b' at index 7.
  20. 20'b' is already in the window at index 4. Any window starting at or before 4 contains it twice — jump the left edge to 5.
  21. 21Window is 3 long. Best stays 4.

The idea

Checking every substring is O(n²) candidates, each needing a duplicate check. But those candidates overlap enormously, and the overlap is the opening.

Keep a window that is always valid — always duplicate-free. Extend it to the right one character at a time. The only thing that can break validity is the character you just added, so that's the only repair you ever need to make.

When the new character was already inside the window, the window has to start after that character's previous position. Not one step right — all the way past it, because any start before that still encloses the duplicate.

The left edge therefore never moves backwards, and the right edge never moves backwards. Two forward-only pointers over n characters is O(n) total, no matter how the string is shaped.

The approach

  1. 1Remember the most recent index of every character seen.
  2. 2Walk the right edge forward one character at a time.
  3. 3If that character was seen before, and that sighting is inside the current window, jump the left edge to just past it.
  4. 4Record the character's new position, then update the best length with the current window size.

Complexity

Time
O(n)
Space
O(k)

Each edge crosses the string once. The map holds at most one entry per distinct character, so k is the alphabet size — often a constant.

Code

def length_of_longest_substring(s):
    last = {}
    best = 0
    left = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

What goes wrong

  • •Forgetting the `last[ch] >= left` check. A duplicate that has already been left behind is not a duplicate any more, and jumping to it drags the left edge backwards, producing lengths that are too small.
  • •Moving the left edge one step at a time when a repeat is found. It's correct but reintroduces the quadratic worst case on strings like "aaaa…".
  • •Reporting the substring instead of its length, or the count of distinct characters — both are different questions.