Longest Substring Without Repeating Characters

StringSliding Window

MediumLeetCode #3

25 min

Problem Statement

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

Example

Example 1:

Input: s = "abcabcbb"

Input: "abcabcbb"

Longest Substring: "abc"

Length: 3

Output: 3

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

Solution (Sliding Window)

The sliding window technique is a perfect fit for this problem. We use a set to keep track of the characters in the current window. When we encounter a character that's already in the set, we shrink the window from the left until the duplicate is removed.

Algorithm Steps

Initialize a set to store characters in the current window, a left pointer at 0, and a result variable to 0.
Iterate through the string with a right pointer.
If the character at the right pointer is already in the set, remove the character at the left pointer from the set and increment the left pointer. Repeat until the duplicate is removed.
Add the character at the right pointer to the set.
Update the result with the maximum of the current result and the size of the current window (right - left + 1).
After the loop, return the result.

Longest Substring Without Repeating Characters

Sliding Window Approach

Progress1 / 1

Ready to start the visualization

String `s`

Character Set

Max Length

Longest Substring Without Repeating Characters Solution


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        chars = set()
        l = 0
        res = 0
        
        for r in range(len(s)):
            while s[r] in chars:
                chars.remove(s[l])
                l += 1
            chars.add(s[r])
            res = max(res, r - l + 1)
        return res