💬 Discord
Sign In
NeetCode #230LC-3MediumSliding WindowBlind 75NC 150NC 250
← Back to All Problems

#230 · #3 · Longest Substring Without Repeating Characters(无重复字符的最长子串)

📌 Problem Statement & Constraints

Given a string s, find the length of the longest substring without repeating characters. Constraints: 0 <= s.length <= 5 * 10^4; s consists of ASCII characters.

💡 Core Algorithmic Approaches

  1. Maintain a window [l, r] containing no duplicate characters, and a map from character to its last seen index.
  2. When s[r] was last seen at index p >= l, the window must jump: l = p + 1.
  3. The window length is then r - l + 1, and the answer is its maximum.
  4. Using the last-seen index (rather than a set with a shrink loop) makes the left pointer jump directly, which is both simpler and faster.

💻 Benchmark Python3 Implementation

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = {}                      # character -> last seen index
        l = 0
        best = 0
        for r, ch in enumerate(s):
            if ch in last and last[ch] >= l:
                l = last[ch] + 1       # jump past the previous occurrence
            last[ch] = r
            best = max(best, r - l + 1)
        return best


# Set-based variant with an explicit shrink loop
class Solution2:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = set()
        l = 0
        best = 0
        for r, ch in enumerate(s):
            while ch in seen:          # shrink until the duplicate is gone
                seen.remove(s[l])
                l += 1
            seen.add(ch)
            best = max(best, r - l + 1)
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each character enters and leaves the window at most once.
💾 Space Complexity
O(k) where k is the size of the character set (at most 128 for ASCII).

⚠️ Interview Pitfalls & Follow-ups

  • Using l = last[ch] + 1 without the last[ch] >= l guard: the left pointer could move backwards, which is wrong. The guard is essential.
  • Comparing last[ch] with 0 instead of l: the relevant question is whether the previous occurrence is inside the current window.
  • Resetting the whole window on a duplicate: that would miss longer windows that start after the first occurrence of the duplicate.
  • Returning the window's length instead of the maximum: the window shrinks over time, so the maximum must be tracked.