[LeetCode/Python] 3. Longest Substring Without Repeating Characters

📌 Problem

[LeetCode] 3. Longest Substring Without Repeating Characters

📌 Solution

Solution 1

Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        ans = 1
        if n == 0:
            return 0

        for left in range(n-1):
            cur = set()
            cur.add(s[left])
            right = left + 1
            while right < n and s[right] not in cur:
                cur.add(s[right])
                right += 1
            ans = max(ans, right - left)

        return ans

Complexity

• Time Complexity: $O(n^2)$ (Worstcase)
  • left=0에서 right가 n까지 가며 n번
  • left=1에서 n-1번 …
• Space Complexity: $O(\min(n, Σ)) ≈ O(n)$

Solution 2

Idea

• 윈도우 [left, right]에는 중복 문자가 없다는 조건 유지

• right를 한 칸씩 늘리며 새 문자 ch = s[right]를 보기

  • ch가 윈도우에 없다면: 그냥 포함 & 길이 갱신하기
  • ch가 이미 있었다면: 윈도우에 중복이 생겼으므로, 이전 ch의 위치 last[ch] 바로 다음으로 left를 점프: left = max(left, last[ch] + 1)
    (※ max가 핵심: 과거의 더 왼쪽 등장 때문에 왼쪽으로 되돌아가면 안 됨)

• 매 스텝에서 last[ch] = right로 갱신하고, ans = max(ans, right - left + 1)로 최장 길이 갱신하기

Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = {}        # char -> last index
        left = 0
        ans = 0

        for right, ch in enumerate(s):
            if ch in last and last[ch] >= left:
                left = last[ch] + 1   # 중복 구간 건너뛰기 (점프)
            last[ch] = right
            ans = max(ans, right - left + 1)
        return ans

• if ch in last and last[ch] >= left: 이 문자(ch)가 윈도우 안에 이미 등장한 적이 있는지 확인

Simulation

s = "abba"
초기: left=0, ans=0, last={}

step	right	ch	조건(ch in last and last[ch] >= left)	left 업데이트	last 갱신	윈도우	ans
1	0	a	False	-	a:0	[0,0]	1
2	1	b	False	-	b:1	[0,1]	2
3	2	b	True (last['b']=1 ≥ left=0)	left=1+1=2	b:2	[2,2]	2
4	3	a	False (last['a']=0 < left=2)	-	a:3	[2,3]	2

Complexity

• Time Complexity: $O(n)$

  • right는 0→n-1까지 정확히 n번
  • left는 뒤로 가지 않고 앞으로만 "점프"하여 총 n번 이내 이동
  • 해시 조회/갱신은 평균 O(1)

• Space Complexity: $O(\min(n, Σ)) ≈ O(n)$

while right < n and s[right] not in cur 에서 순서 주의!
while s[right] not in cur and right < n 라고 쓰면 s[right] 조회 시 index error 발생함