[LeetCode/Python] 3. 중복 문자 없는 가장 긴 문자열(Longest Substring Without Repeating Charactors)

중복 문자가 없는 가장 긴 부분 문자열(Substring)의 길이를 리턴하라.

 

Input: s = "abcabcbb"

 

Output: 3

 

Explanation: The answer is "abc", with the length of 3.

 

 

 

보통 문자열이나 리스트를 대상으로 여러 인덱스를 앞에서부터 비교해나가는 문제는

 

투 포인터나 슬라이딩 윈도를 이용하여 해결할 수 있다.

 

 

 

** 깔끔한 답안 **

 

 

 

1. 슬라이딩 윈도우와 투 포인터로 사이즈 조절

 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_length = start = 0
        for index, char in enumerate(s):
            # 이미 등장했던 문자라면 'start' 위치 갱신
            if char in used and start <= used[char]:
                start = used[char] + 1
            else:  # 최대 부분 문자열 길이 갱신
                max_length = max(max_length, index - start + 1)
 
            # 현재 문자의 위치 삽입
            used[char] = index
 
        return max_length
 

 

해설:

 

위 코드에서 start가 left, index가 right인 투 포인터라고 생각할 수 있다.

 

used에 존재하지 않는 문자가 있으면 지속적으로 max를 통해 최대 부분 문자열 길이를 갱신해주고

 

used에 현재 문자와 함께 인덱스 값을 넣어준다.

 

이런 식으로 진행하다가 이미 등장했던 문자가 등장하면 start를 이전에 등장한 문자의 그다음으로 바꿔준다.

 

( s = "abcabcbb"로 진행해보면 이해가 쉽다)

 

 

 

 

 

 

[출처: 파이썬 알고리즘 인터뷰(박상길 지음 / 정진호 일러스트 / 출판사 책만)]