[파이썬 알고리즘 인터뷰][해시테이블] 중복 문자 없는 가장 긴 부분 문자열

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

중복 문자가 없는 가장 긴 부분 문자열의 길이 리턴

 

책에서 구현된 코드

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

 

기억해야할 기법

• 인덱스와 값을 모두 활용할 땐 enumerate

 

내가 구현한 코드

def lengthOfLongestSubstring(s: str) -> int:
    start = max_len = 0
    dic = defaultdict(int)

    for i in range(len(s)):
        end = i + 1
        c = s[i]
        if dic[c] == 0:
            dic[c] = end
        else:
            start, dic[c] = max(dic[c], start), end
        max_len = max(end - start, max_len)
    return max_len

• 책과 비슷한 형태로 만든 것 같은데 성능 차이가 크다
• defaultdict 사용할 필요 없이, key만 dict에 존재하는지 확인하면 된다
• 내가 구현한 코드에서 if-else의 dic[c] = end가 두 구문에 모두 포함된다(중복)
• max_len은 길이가 늘어날 때만 계산하면 된다
  • 책에서는 if-else를 max 계산 여부로 나눔
• 내가 구현한 알고리즘

• 책에서 구현한 알고리즘