Python으로 푸는 LeetCode 3. Longest Substring Without Repeating Characters (Medium)

LeetCode 3. Longest Substring Without Repeating Characters (Medium)

서로 다른 문자로 이루어진 가장 긴 문자열을 찾을 수 있도록 코드를 짜야한다.

LeetCode에서 푼 문제 리스트 보기

LeetCode에서 문제 보기

github에서 코드 보기

문제 풀이

1 이하의 문자는 그 길이를 구해 반환해준다.  그 외에는 처음 문자부터 서로 다른 문자일 경우를 확인해서 count를 해준다.

이미 나왔던 문자일 경우를 찾아내는 방법은 다음과 같다. 처음 보는 문자일 경우 defaultdict()에 그 문자를 key로 하고 index를 값으로 하여 ch_dict에 값을 구해둔다. 만약 이미 나왔던 문자가 나왔을 경우에는 ch_dict를 뒤져보았을 때, 해당 문자를 key로 하는 index 값이 존재할 것이다. 그러면 지금까지 세왔던 count 값과 max_count와 비교해 최대값을 구해준다. 다음 탐색은 ch_dict에 잇었던 index+1 부터 재탐색 하면 된다. 그 이후에는 ch_dict, count를 초기화해준다.

파이썬 코드ithout Repeating Characters 파이썬 

from collections import defaultdict

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        if len(s) < 2:
            return len(s)

        ch_dict = defaultdict(lambda : -1)
        cur_idx = 0
        length = len(s)
        cur_count = 0
        max_count = 1

        while cur_idx < length:
            ch = s[cur_idx]
            # dict에 해당 문자가 현재 체크하는 범위 내에 존재하지 않으면 (0 이하 포함)
            idx = ch_dict[ch]
            if idx == -1:
                ch_dict[ch] = cur_idx
                cur_count += 1
            else:
                max_count = max(cur_count, max_count)
                before_ch_idx = ch_dict[ch]
                # 중복된 문자열 다음부터 문자 비교를 위해 count, start_idx 수정

                start_idx = before_ch_idx + 1
                # 바로 옆과 일치하는 경우
                if before_ch_idx == (cur_idx - 1):
                    start_idx = cur_idx
                # 재 탐색 위치 수정
                cur_idx = before_ch_idx
                cur_count = 0
                ch_dict = defaultdict(lambda: -1)
                # 더이상 체크할 필요 없는 경우
                if length - start_idx <= max_count:
                    break
            cur_idx += 1
        # 마지막으로 한번 더 비교
        max_count = max(cur_count, max_count)
        return max_count