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

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

반복되는 문자 없이 가장 긴 substring의 길이를 찾는 문제!

substring은 시작과 끝이 정의된 유동적인 범위이므로,

상황에 따라 범위(윈도우)를 늘리거나 줄이는 슬라이딩 윈도우 풀이를 떠올릴 수 있다. 

 

 

풀이 : Sliding Window

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charSet = set()
        l = 0
        res = 0

        for r in range(len(s)):
            while s[r] in charSet:
                charSet.remove(s[l])
                l += 1
            charSet.add(s[r])
            res = max(res, r - l + 1)
        return res

• charSet: 중복 검사를 위한 집합(set)
• l (왼쪽 포인터): 현재 확인 중인 substring의 시작
• r (오른쪽 포인터): 문자열 탐색하며 현재 문자를 가리킴

 

1. 중복 문자가 있는 경우

• s[r]이 이미 charSet에 있다면, 중복을 제거하기 위해 charSet.remove(s[l])로 문자를 제거하고, l 포인터를 오른쪽으로 이동
• s[l:r] 부분 문자열이 다시 중복 없는 상태가 될 때까지 반복

2. 중복 없는 경우

• 현재 문자 s[r]을 charSet.add(s[r])로 추가
• 이후 현재 구간의 길이를 계산하여 res에 최댓값을 갱신

 

r포인터가 문자열 전체를 한 번만 순회하고 l 포인터도 최대 n번 이동하므로 시간 복잡도는 O(n)이다.

공간 복잡도는 문자 집합의 크기가 k라고 했을 때 O(k)이다.