0003.Longest Substring wo Repeating Characters

Link: 3. Longest Substring Without Repeating Characters
Track: NeetCode150

Question

Restate the problem

• Given a String s
• Find the length of the longest substring without repeating characters
• Return int

Edge Case

• if not s, return 0

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Sliding window	$O(n)$	$O(n)$

Method 1: Sliding window

Key idea: Maintain a window [left, right] that is always valid (no character count > 1); expand right, and when a duplicate appears, shrink from left until valid again.

Approach

1. Expand the window by moving right and adding s[right]
2. While the window is invalid (a duplicate exists),
   • Shrink by moving left and removing s[left]
3. Update the max length after the window becomes valid

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
        left = right = 0
        length = 0
        while right < len(s):
            dic[s[right]] = dic.get(s[right], 0) + 1
            
            while dic[s[right]] > 1:
                dic[s[left]] -= 1
                left += 1
            
            length = max(length, right - left + 1)
            
            right += 1
        
        return length

---

Common Mistake

• Must use while dic[s[right]] > 1 because you may need to move left multiple steps to remove the duplicate.