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

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브

 

---

30. 중복 문자 없는 가장 긴 부분 문자열

leetcode 3. Longest Substring Without Repeating Characters 문제입니다.

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

 

 

풀이

 s를 enumerate로 index와 char을 하나씩 꺼냅니다.

 char에 해당하는 index를 dictionary에 저장하고, char가 이미 dictionary에 저장되어 있으면 중복 문자입니다.

 이 경우에 start를 변경해줍니다.

 

def lengthOfLongestSubstring(self, s):
    used = {}
    start = max_len = 0
    for index, char in enumerate(s):
        if char in used and start <= used[char]:
            start = used[char] + 1
        else:
            max_len = max(max_len, index - start + 1)

        used[char] = index

    return max_len