LeetCode 3 - Longest Substring Without Repeating Characters

This Medium string problem asks for the longest substring with no repeated characters. Because a substring must be contiguous, I used a sliding window and a set containing exactly the characters in the current window.

---

Problem link and explanation

• Problem: 3. Longest Substring Without Repeating Characters
• Summary: Given a string s, return the maximum length of a contiguous substring in which every character is unique.

The right boundary advances one character at a time. If that character already exists in the window, the left boundary advances until the duplicate has been removed. The resulting valid window can then update the maximum length.

---

Approach

chars stores the current window’s characters, and left marks its starting index. enumerate supplies the right boundary and incoming character.

chars = set()
left = 0
longest = 0

for right, char in enumerate(s):

When the incoming character is already present, the loop removes characters from the left. This must be a while, not an if, because the duplicate may be somewhere in the middle of the current window rather than at its first position.

while char in chars:
    chars.remove(s[left])
    left += 1

After the duplicate is gone, the incoming character can be added. The window is valid at this point, so its length is right - left + 1.

chars.add(char)
longest = max(longest, right - left + 1)

Although the code contains a nested loop, neither pointer moves backward. A character enters the set once when the right boundary reaches it and leaves at most once when the left boundary passes it.

---

Complexity analysis

• Time complexity: O(n)
  • Every character is added to the set at most once and removed at most once.
• Space complexity: O(n)
  • If every character is unique, the set may contain the entire string. With a fixed character alphabet, the alphabet size provides a tighter upper bound.

---

Implementation code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        chars = set()
        left = 0
        longest = 0

        for right, char in enumerate(s):
            while char in chars:
                chars.remove(s[left])
                left += 1

            chars.add(char)
            longest = max(longest, right - left + 1)

        return longest

---

Summary and reflection

The set maintains the window invariant: every character between left and right is unique. On a duplicate, the left side must shrink until that exact character leaves the set before the window becomes valid again. The nested loop does not make the algorithm quadratic because both boundaries cross the string only once in the forward direction.