Longest Substring Without Repeating Characters – Sliding Window Explained (Python)

Longest Substring Without Repeating Characters (Sliding Window)

This problem is one of the most important questions to understand the Sliding Window pattern. The goal is to find the length of the longest substring that contains only unique characters.

Problem Statement

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

Intuition

A substring is always continuous, which makes this problem a perfect candidate for the sliding window technique. We maintain a window that always contains unique characters.

Whenever a duplicate character appears, we shrink the window from the left until the duplicate is removed. At every step, we track the maximum window size.

Approach

• Use two pointers l (left) and r (right).
• Use a set to store characters in the current window.
• Expand the window by moving r.
• If a duplicate is found, shrink the window by moving l.
• Update the maximum length after each valid window.

Python Solution

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l = 0
        r = 0
        max_len = 0
        window = set()

        while r < len(s):
            if s[r] in window:
                window.remove(s[l])
                l += 1
            else:
                window.add(s[r])
                r += 1

            max_len = max(max_len, len(window))

        return max_len

Example Walkthrough

For input "abcabcbb":

• "abc" → length 3 (valid)
• Next "a" causes repetition → shrink window
• Continue sliding and updating max length

Final Answer: 3

Time & Space Complexity

• Time Complexity: O(n) — each character is processed at most twice.
• Space Complexity: O(min(n, charset)) — set stores unique characters.

Key Takeaway

If a problem involves substrings, continuous ranges, and constraints like "no duplicates" or "at most k", the Sliding Window pattern is usually the optimal solution.

Mastering this pattern will help solve many similar problems efficiently.