[LeetCode] 3. Longest Substring Without Repeating Characters

문제 보기

 

[사용한 알고리즘]

슬라이딩 윈도우 (Sliding Window)

 

[설명]

사실 문제 봤을 때 슬라이딩 윈도우 알고리즘이 떠오르지 않았다. 뭔가 풀어본 문제인데 '어떻게 풀었지?'를 5번 이상 반복했다. 결국 집합(set)과 left, right 인덱스 두 개를 활용하도록 나만의 설계를 작성한 후 코드를 구현하였다. 하지만, 구현 후 코드를 다시 확인해보니 나만의 설계가 아니라 그냥 슬라이딩 윈도우 그 자체였다. 그래도 약 2년 전에 열심히 코딩 테스트 준비하였던 경험들이 아직 머릿속에 조금은 남아있는 듯하다. 알고리즘은 크게 어렵지 않다.

 

문자열 s의 길이가 2미만인 경우 문자열 s의 길이를 반환한다. 문자열 s의 길이가 2이상인 경우 중복 없는 최대 부분 문자열을 찾기 위해서 반복문을 수행한다. 반복문 중 대부분의 코드는 별도의 설명이 없어도 이해하기 쉽기 때문에 핵심만 설명하고자 한다. s[right] 값이 substring 집합에 포함된 경우 left 인덱스 값을 업데이트해야 한다. 예를 들어 "pwwkew"에서 right 값이 2인 경우 substring에 이미 'w'가 포함되어있다. 따라서, left 값을 0에서 2로 업데이트해야한다. 이런 식으로 left, right인덱스 값을 조절하여 2중 for 문보다 효율적으로 Longest Substring을 찾을 수 있다.

 

[코드]

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

        output = 0
        left, right = 0, 1
        substring = set(s[0])

        while left <= right < len(s):
            
            if s[right] in substring:
                while s[left] != s[right]:
                    substring.remove(s[left])
                    left += 1
                left += 1
            elif s[right] not in substring:
                substring.add(s[right])

            output = max(output, right - left + 1)
            right += 1
        return output