[LeetCode] #3. Longest Substring Without Repeating Characters (python)

문제

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

중복 문자가 없는 부분 문자열 중 가장 긴 길이를 반환하면 된다.

 

예시 입출력

Input:
s = "abcabcbb"
Output:
3

 

풀이

 

책 풀이

슬라이딩 윈도우와 투 포인터

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의 위치를 갱신해서 이전에 나온 문자열이 포함되지 않게 한다. 처음 보는 문자라면 max함수로 최대 길이를 확인하고 현재 문자의 위치를 갱신한다.

start의 위치를 갱신할 때 바로 위치를 갱신시키면 안되고 현재 슬라이딩 윈도우 안에 있어야 하기 때문에 start≤used[char] 조건이 있어야 한다.

max 함수로 최대 길이를 비교할 때는 max_length와 현재문자열을 마지막으로 하는 부분 문자열의 길이를 비교한다.

 

 

참고한 책 : 파이썬 알고리즘 인터뷰