3. Longest Substring Without Repeating CharactersMedium

Longest Substring Without Repeating Characters

MediumHash TableStringSliding Window·AmazonGoogleMicrosoftMeta

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

Example 1:

Input:s = "abcabcbb"

Output:3

The answer is "abc", with the length of 3.

Example 2:

Input:s = "bbbbb"

Output:1

The answer is "b", with the length of 1.

Example 3:

Input:s = "pwwkew"

Output:3

The answer is "wke", with the length of 3.

Constraints:

0 ≤ s.length ≤ 5 × 10⁴
s consists of English letters, digits, symbols and spaces.

Hints

Hint 1How would you detect a duplicate character efficiently?▼

Use a HashSet to track which characters are currently in your window. Lookup and insert are both O(1). When you find s[r] already in the set, you have a duplicate.

Hint 2When a duplicate is found at r, how far do you need to move l?▼

You must advance l until s[r] is no longer in the set. Keep removing s[l] from the set and incrementing l until the duplicate is gone.

Hint 3What is the time complexity? Can we do better than O(2n)?▼

The two-pointer approach is O(n) — each character is added and removed at most once. For a slight constant improvement, use a HashMap to store the last-seen index of each character and jump l directly past the duplicate.

🌐 Real-World Analogy

Network Packet Deduplication

Network routers must detect and drop duplicate packets in a stream. A sliding window keeps track of only the packets in the current "fresh" window — using a hash set for O(1) lookup. When a duplicate arrives, the window shrinks from the left until the duplicate is evicted, then the new packet is added. This is exactly the two-pointer algorithm — and it processes millions of packets per second with O(n) time and O(k) space (where k is the alphabet/charset size).

Optimal Approach — Variable Sliding Window + HashSet

O(n) Time

🔤

Two Pointers + Set — Expand R, Shrink L on Duplicate

Time O(n)Space O(k)

This is a variable-size sliding window problem. The window [l, r] always contains unique characters. We grow it by advancing r, and shrink from the left whenever a duplicate is detected.

1Initialize charSet = set(), l = 0, res = 0.
2Advance r through the string. If s[r] is already in charSet, remove s[l] and increment l until the duplicate is gone.
3Add s[r] to charSet.
4Update res = max(res, r - l + 1).
5Return res.

Each character is inserted and removed from the set at most once, so total work is O(n). Space is O(k) where k is the character set size (at most 128 for ASCII).

String — L pointer (left edge) · R pointer (right edge)

charSet — current characters in window

empty set

READY—

Press ▶ or step forward to begin.

l—

r—

res—

✓

—

String

Space Play/Pause·←→ Step·R Reset

Executing Code

def lengthOfLongestSubstring(s):

    charSet = set()

    l = 0

    res = 0

    for r in range(len(s)):

        while s[r] in charSet:

            charSet.remove(s[l])

            l += 1

        charSet.add(s[r])

        res = max(res, r - l + 1)

    return res

Discussion

…

Loading comments…

LeetMotion

Longest Substring Without Repeating Characters

MediumHash TableStringSliding Window·AmazonGoogleMicrosoftMeta

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

Example 1:

Input:s = "abcabcbb"

Output:3

The answer is "abc", with the length of 3.

Example 2:

Input:s = "bbbbb"

Output:1

The answer is "b", with the length of 1.

Example 3:

Input:s = "pwwkew"

Output:3

The answer is "wke", with the length of 3.

Constraints:

0 ≤ s.length ≤ 5 × 10⁴
s consists of English letters, digits, symbols and spaces.

Hints

Hint 1How would you detect a duplicate character efficiently?▼

Use a HashSet to track which characters are currently in your window. Lookup and insert are both O(1). When you find s[r] already in the set, you have a duplicate.

Hint 2When a duplicate is found at r, how far do you need to move l?▼

You must advance l until s[r] is no longer in the set. Keep removing s[l] from the set and incrementing l until the duplicate is gone.

Hint 3What is the time complexity? Can we do better than O(2n)?▼

🌐 Real-World Analogy

Network Packet Deduplication

Optimal Approach — Variable Sliding Window + HashSet

O(n) Time

🔤

Two Pointers + Set — Expand R, Shrink L on Duplicate

Time O(n)Space O(k)

This is a variable-size sliding window problem. The window [l, r] always contains unique characters. We grow it by advancing r, and shrink from the left whenever a duplicate is detected.

1Initialize charSet = set(), l = 0, res = 0.
2Advance r through the string. If s[r] is already in charSet, remove s[l] and increment l until the duplicate is gone.
3Add s[r] to charSet.
4Update res = max(res, r - l + 1).
5Return res.

Each character is inserted and removed from the set at most once, so total work is O(n). Space is O(k) where k is the character set size (at most 128 for ASCII).

String — L pointer (left edge) · R pointer (right edge)

charSet — current characters in window

empty set

READY—

Press ▶ or step forward to begin.

l—

r—

res—

✓

—

String

Space Play/Pause·←→ Step·R Reset

Executing Code

def lengthOfLongestSubstring(s):

    charSet = set()

    l = 0

    res = 0

    for r in range(len(s)):

        while s[r] in charSet:

            charSet.remove(s[l])

            l += 1

        charSet.add(s[r])

        res = max(res, r - l + 1)

    return res