[leetcode] 3. Longest Substring Without Repeating Characters 풀이

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        answer = 0
        length = len(s)
        dic = {}
        i = 0
        for j in range(0, length):
            if s[j] in dic:
                i = max(i, dic[s[j]]+1)
            dic[s[j]] = j
            answer = max(answer, j - i + 1)
            # print('j:',j,'i:',i,'answer:',answer)
        return answer

 

문제

• 연속된 스트링이 주어짐 (e.g., abdeacde)
• 가장 긴 유니크한 스트링 셋을 찾아야 함 (e.g., abde)

방안

• 무식하게 모든 스트링을 체크해서 가장 긴 substring을 찾음 (Timeout)
• window을 이동시켜서 가장 긴 substring을 찾음
• window 크기는 발견된 character 위치 혹은 가장 값이 큰 i 값 (window 기준값)을 선택해서 크기를 결정한다.