LeetCode 3 - Longest Substring Without Repeating Characters

문자열에서 중복 문자가 없는 가장 긴 substring의 길이를 구하는 Medium 문제다. substring은 연속된 구간이어야 하므로, 현재 구간에 어떤 문자가 들어 있는지 set으로 관리하는 sliding window를 사용했다.

문제 링크 & 설명

문제 링크: 3. Longest Substring Without Repeating Characters
요약: 문자열 s에서 같은 문자가 두 번 나타나지 않는 연속 부분 문자열 중 가장 긴 길이를 반환한다.

오른쪽 포인터를 한 칸씩 이동하며 새 문자를 윈도우에 넣는다. 새 문자가 이미 윈도우 안에 있다면 중복이 없어질 때까지 왼쪽 포인터를 이동한 뒤, 현재 윈도우의 길이로 최댓값을 갱신한다.

접근 방법

chars에는 현재 윈도우의 문자만 저장하고, left는 윈도우의 시작 위치를 가리킨다. right와 현재 문자는 enumerate로 순서대로 얻는다.

chars = set()
left = 0
longest = 0

for right, char in enumerate(s):

현재 문자가 set에 있으면 left가 가리키는 문자를 제거하면서 왼쪽 경계를 줄인다. if가 아니라 while을 사용하는 이유는, 중복된 문자가 윈도우 왼쪽 끝에 있다는 보장이 없기 때문이다.

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

중복이 제거되면 현재 문자를 추가한다. 이 시점의 윈도우는 중복 문자가 없는 유효한 구간이므로 right - left + 1로 길이를 계산한다.

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

각 문자는 오른쪽 포인터가 방문할 때 set에 한 번 들어가고, 왼쪽 포인터가 지나갈 때 최대 한 번 제거된다. 중첩된 while이 있어도 두 포인터는 뒤로 이동하지 않는다.

복잡도 분석

시간 복잡도: O(n)
- 각 문자는 set에 최대 한 번 추가되고 최대 한 번 제거된다.
공간 복잡도: O(n)
- 최악의 경우 문자열의 모든 문자가 서로 달라 set에 전체 문자가 저장된다. 문자 집합의 크기가 고정되어 있다면 그 크기로 상한을 둘 수 있다.

구현 코드

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

요약 및 회고

이 풀이에서 set은 현재 윈도우가 중복 없는 구간이라는 조건을 유지한다. 중복 문자를 만났을 때 왼쪽을 한 번만 옮기는 것이 아니라 해당 문자가 빠질 때까지 줄여야 다시 유효한 윈도우가 된다. 중첩 반복문만 보면 O(n²)처럼 보일 수 있지만, 각 포인터가 문자열 전체를 한 방향으로 한 번씩 지나간다는 기준으로 보면 O(n)임을 확인할 수 있다.