알고리즘 - 중복 문자 없는 가장 긴 부분 문자열

리트코드 3번 문제

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

Input Output
s = “abcabcbb” 3
s = “bbbbb” 1
s = “pwwkew” 3



Solution(슬라이딩 윈도우와 투포인터로 사이즈 조절)Permalink

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

start는 첫번째 포인터 역할,
used는 현재 문자를 키로 하고 인덱스를 값으로 하는 끝 포인터 역할을 한다.

현재 문자의 인덱스 값을 저장할텐데
현재 문자가 중복되서 사용됬다면 첫번째 포인터를 앞으로 이동시킨다.
아니라면 현재 저장된 최대값과 현재 인덱스 - 시작 인덱스 + 1 한 값을 비교하여 큰 값을 max_length에 넣는다.

중복값처리와 포인터 역할을 하는 해시 테이블을 만든다는 생각을 하는 것이 키포인트였던것 같다.

댓글남기기