Longest Substring Without Repeating Characters | Leetcode 3

Welcome to our deep dive on Longest Substring Without Repeating Characters (Leetcode 3). This extremely popular problem is the ultimate test of your Sliding Window skills.

Problem Statement

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

Example 1: s = "abcabcbb" => Output: 3 (Explanation: The answer is "abc", with the length of 3.)

Example 2: s = "bbbbb" => Output: 1

Example 3: s = "pwwkew" => Output: 3 (Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.)

Approach: Sliding Window + HashMap O(N)

The brute force method involves checking every possible substring O(N^3). By employing a Sliding Window, we can parse the string in a single linear pass O(N).

We use two pointers, left and right, to define our current "window" (the substring). We expand right to process new characters. If we see a character we've never seen before, our window grows and we update our max length. If we have seen the character before, we must shrink the window from the left until that duplicate character is ejected!

We can optimize this shrinking process by storing the exact index of every character in a HashMap. Instead of slowly incrementing left by 1, we can instantly jump left directly past the previous occurrence of the duplicate character!

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_map = {}
        left = 0
        max_len = 0
        
        for right in range(len(s)):
            char = s[right]
            
            # If we've seen this character AND it's physically inside our current window
            if char in char_map and char_map[char] >= left:
                # Instantly shrink the window by jumping 'left' past the old duplicate
                left = char_map[char] + 1
                
            # Update the latest index of the character
            char_map[char] = right
            
            # Calculate the current valid window length
            max_len = max(max_len, right - left + 1)
            
        return max_len

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (3)