[리트코드][Medium] Longest Substring Without Repeating Characters

문제

리트코드 Longest Substring Without Repeating Characters

자료구조 및 알고리즘

• dictionary, set

• sliding window

문제 풀이 및 회고

푸는데 30분 정도 걸렸지만 제출을 여러번 하고도 실패했고 성공했어도 너무 좋은 로직이 있어서 글 남기고자 작성하였다.

내 풀이

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        answer = 0
        n = len(s)
        DICT = {}
        
        for i in range(n):
            if s[i] not in DICT: # s[i]가 처음 들어왔을 때
                DICT[s[i]] = set()
                DICT[s[i]].add(s[i])
                for k, v in DICT.items(): # 모든 글자들에 추가
                    DICT[k].add(s[i])
            else: # 기존에 있는 것들이랑 겹쳐서 들어왔을 때
                for k, v in DICT.items(): # 모든 글자들에 대해서
                    if s[i] in v: # 이미 들어온 적이 있으면 wkw, wjkwlkw ...
                        answer = max(answer, len(v))  # 길이 비교하고
                        del DICT[k] # 제거하고
                    else:
                        DICT[k].add(s[i]) # 들어온 적이 없으면 또 길이 추가
                DICT[s[i]] = set() # D[s[i]] 갱신
                DICT[s[i]].add(s[i])
        values = DICT.values()
        for i in range(len(values)): # 길이 비교하기 위해서
            values[i] = len(values[i])
        answer = max(values + [answer]) # 한번에 결과찾기
        
        return answer

가장 간단한 풀이

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        seen = {} # dictionary로 각 문자의 마지막 인덱스 기록
        l = 0 # 부분 문자열의 시작 인덱스
        length = 0 # 반복되지 않는 가장 긴 부분의 문자열 길이(정답이 될 친구)
        for r in range(len(s)):
            char = s[r]
            if char in seen and seen[char] >= l: # 본적이 있고 그 위치가 현재 "부분의 문자열 시작 인덱스"보다 크거나 같다면
                l = seen[char] + 1 # 부분 문자열의 시작 인덱스를 갱신하여 반복된 문자 이후로 이동
            else:
                length = max(length, r - l + 1) # 반복되지 않은 부분 문자열의 길이를 갱신
            seen[char] = r # 마지막으로 본 idx 저장

        return length

메모리를 좀 더 최적화한 코드

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        seen = {}
        l, length = 0, 0
        
        for r, char in enumerate(s):
            if char in seen and seen[char] >= l:
                l = seen[char] + 1
            length = max(length, r - l + 1)
            seen[char] = r
        
        return length