LeetEye LeetEye
Medium Sliding Window ~5 min

Longest Substring Without Repeating Characters

sliding-window longest-substring-without-repeating-characters

Problem

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

Examples

Example 1
Input: s = "abcabcbb"
Output: 3
The answer is "abc", with length 3.
Example 2
Input: s = "bbbbb"
Output: 1
The answer is "b", with length 1.
Example 3
Input: s = "pwwkew"
Output: 3
The answer is "wke", with length 3.
Key Insight

Expand the window right. When a duplicate is found, shrink from the left until unique again.

Sliding window with set: expand right, shrink left until no duplicate, track max window size.

How to Approach This Problem

Pattern Recognition: When you see keywords like longest substring without repeating characters sliding-window, think Sliding Window.

Step-by-Step Reasoning

1 A window (substring) is valid if:
Answer: All characters in it are unique
"Without repeating characters" means all unique within the window.
2 We can expand the window by moving the right pointer when:
Answer: The new character is not in the current window
Adding a character that's already in the window creates a duplicate, violating our constraint.
3 We must shrink the window (move left pointer) when:
Answer: The character at right pointer already exists in window
A duplicate means the window is invalid. Shrink until the duplicate is removed.
4 When shrinking due to duplicate at position r, shrink until:
Answer: The duplicate character is no longer in the window
We only need to remove enough to eliminate the duplicate. Then we can include s[r].
5 To check if a character is in the current window in O(1):
Answer: Use a hash set
Set provides O(1) add, remove, and contains operations.
6 If we track each character's last position, when we find duplicate:
Answer: We can jump left pointer to last_position[char] + 1
If we know where the duplicate was last seen, we can jump past it. This is still O(n) but with fewer operations.

Solution

def lengthOfLongestSubstring(s: str) -> int:
    char_set = set()
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        # Shrink window until no duplicate
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    
    return max_len

Complexity Analysis

Time O(n)
Space O(min(n, alphabet))

Master This Pattern

Build intuition with interactive MCQs. Practice Sliding Window problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye