[리트코드] 3. 중복 문자가 없는 가장 긴 부분 문자열 (Python)

Longest Substring Without Repeating Characters - LeetCode

문제

중복 문자가 없는 가장 긴 부분 문자열을 구해라

 

과정

1. 이미 사용된 문자를 저장할 리스트와 최대 길이, 시작 포인트 변수를 만든다.
2. 입력을 받은 문자열의 각 문자들을 enumerate를 통해 확인한다.
3. 이미 등장했던 문자라면 start의 위치를 갱신해준다.
4. 그게 아니라면 최대 부분 문자열의 길이를 갱신해준다.

 

입력

"abcabcbb"

출력

3

 

풀이

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_length = start = 0
        for index, char in enumerate(s):
            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

 

한 줄씩 코드 해석해보기

used = {}
max_length = start = 0

• 이미 사용된 문자를 저장할 리스트와 최대 길이, 시작 포인트 변수를 만든다.

for index, char in enumerate(s):

• enumerate()를 이용해 index와 문자를 확인한다.

if char in used and start <= used[char]:
    start = used[char] + 1

• 이미 등장했던 문자라면 start의 위치를 갱신한다

else:
    max_length = max(max_length, index - start + 1)

• 그게 아니라면 최대 부분 문자열의 길이를 갱신해준다.

used[char] = index

• 사용된 문자를 확인하기 위해 현재 문자의 위치를 삽입한다

return max_length

• 최대 길이값 출력