[LeetCode] 3. Longest Substring Without Repeating Characters

I. Description

문제 링크: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/?envType=problem-list-v2&envId=hash-table&

---

II. Code

i)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = max_len = 0
        char_set = set()
        
        # right 포인터를 옮겨가며
        for right in range(len(s)):
        	# 중복 문자 나오면 중복 문자 없을 때까지 left 포인터 옮기기
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1
            char_set.add(s[right])
            
            # 최대 길이 갱신
            max_len = max(max_len, right - left + 1)
            
        return max_len

left, right 2개의 포인터를 움직여가며 max_len을 업데이트하는 방식이다.

ii)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = max_len = 0
        count = {}
        
        for right, c in enumerate(s):
        	# count dict의 key: 문자, value: 개수
            count[c] = 1 + count.get(c, 0)
            # 중복 문자가 있을 경우 left 포인터 이동 (중복 문자가 없을 때까지)
            while count[c] > 1:
                count[s[left]] -= 1
                left += 1
                
            # 최대 길이 갱신
            max_len = max(max_len, right - left + 1)
            
        return max_len

방법은 동일하나 Hash table 방식을 사용하여 살짝 변형한 것이다.

iii)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = max_len = 0
        last_seen = {}
        
        for right, c in enumerate(s):
            if c in last_seen and last_seen[c] >= left:
                left = last_seen[c] + 1
                
            max_len = max(max_len, right - left + 1)
            last_seen[c] = right
            
        return max_len

dict의 value를 개수 대신 포인터 위치처럼 보게 해서 구할 수도 있다.

 

해답 출처: https://leetcode.com/problems/longest-substring-without-repeating-characters/solutions/5111376/video-3-ways-to-solve-this-question-sliding-window-set-hashing-and-the-last-position

 

실패)

iV)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        store_dict = {} # Key: substring, Value: length
        temp = {}   # Swap을 위한 변수
        max_len = 0 # 최대 길이
        for alpha in s:
            temp = store_dict.copy()
            
            # 최대 길이 갱신
            if max(store_dict.values(), default=0) > max_len:
                max_len = max(store_dict.values(), default=0)
                
            # Ex) 'dvdk'
            # {'d': 1} -> {'dv': 2, 'v': 1} / {'dv': 2, 'v': 1} -> {'vd': 2, 'd': 1}
            for key, value in store_dict.items():
                if alpha not in key:
                    temp[key + alpha] = value + 1
                del temp[key]
            temp[alpha] = 1
            store_dict = temp
            
        return max(max_len, max(store_dict.values(), default=0))

dict를 활용한 방법으로 풀어보려 했다. 생각해보니 dict의 value를 length로 안 둬도 되겠다는 생각이 들었다. Key의 길이가 length니까. 그래서 두 번째 방법을 시도해보았다.

V)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        store_dict = {}
        temp = {}
        for alpha in s:
            temp = store_dict.copy()
            
            for key, value in store_dict.items():
                if value == True:
                    if alpha not in key:
                        temp[key + alpha] = True
                    temp[key] = False
            temp[alpha] = True
            store_dict = temp
        return max((len(key) for key in store_dict.keys()), default=0)

두 번째 방법에서는 중복 없는 모든 substring을 dict로 가지고 있는 것은 어떨까 생각했다. 따라서 True와 False를 value로 둬서 alpha를 추가하는가, 안 하는가의 기준을 세웠다. i), ii) 방법 모두 매우 Runtime이 길었다. 다른 방법이 생각나지 않아 Solution을 찾아보았다.

---

III. What I Learned

이 문제의 답변에 대해 오래 고민하면서 깨달은 게 있다. 그동안은 코딩테스트가 실무와 연관이 적다고 생각했다. 그런데 며칠 전에 오늘의집 일을 하면서 내가 코드를 비효율적으로 짜고 있다는 느낌이 들었다. 여러 함수에서 변수를 유지하고 정의를 최소화하는 방법을 몰라 코드를 반복해서 작성하는 기분을 받았다. 아, 이러한 데서 코딩테스트, 즉 알고리즘을 공부한 게 의미가 있겠구나 라는 생각이 들었다. 개발 분야나 일마다 사용하는 툴, 해야 하는 일은 다르겠지만 이걸 효율적으로 짜고 최적화시키는 데는 공통적으로 알고리즘이 작동하겠구나, 그래서 회사에서 코딩테스트 시험을 보는 거구나 라는 생각이 들었다. 꼭 코딩테스트를 공부한다는 생각보다 코딩의 가장 근간이 되는 알고리즘을 공부한다는 생각으로 더 열중하려 한다.