Longest Substring Without Repeating Characters

문제

Given a string s, find the length of the longest substring without repeating characters.

풀이

• left: 삭제, right: 추가
• 현재 left와 right 사이의 문자를 관리하는 defaultdict(int) 사용했다.
• 만약 counter[s[right]]가 2개 이상이라면 중복된 문자가 있는 문자열이므로 하나만 남을 수 있도록 제거해야 한다.
• 현재 문자열 길이가 최대가 되도록 answer를 갱신한다.

s = "abcabcbb"
'a': counter = {'a': 1}, substring = "a"
'b': counter = {'a': 1, 'b': 1}, substring = "ab"
'c': counter = {'a': 1, 'b': 1, 'c': 1}, substring = "abc"
'a': 중복이 발생하므로 제거, start = 1로 이동, substring = "bca"
'b': 중복이 발생하므로 제거, start = 2로 이동, substring = "cab"
'c': 중복이 발생하므로 제거, start = 3로 이동, substring = "abc"
...

수도코드

right = left = answer = 0
cnt = 딕셔너리

for s의 처음부터 끝까지:
	cnt[right가 가리키는 s 문자]++
    
    while cnt[right가 가리키는 s 문자]가 두개 이상이라면:
    	cnt[left가 가리키는 s 문자]--
        left++
    answer = max(answer, right - left + 1) # 길이 갱신

Solution(Runtime: 34ms)

from collections import defaultdict

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        left = answer = 0
        cnt = defaultdict(int)
        
        for right, now in enumerate(s):
            cnt[now] += 1

            while cnt[now] > 1:
                cnt[s[left]] -= 1
                left += 1

            answer = max(answer, right - left + 1)
        
        return answer

나는 딕셔너리를 썼지만, 딕셔너리처럼 O(1)에 바로 값을 찾을 수 있는 자료구조(set..)라면 사용할 수 있다.

• 다른사람의 코드를 수정한 코드

max_len = 0
pos = defaultdict(int) # 문자열의 위치를 저장하는 딕셔너리
start = 0

for end, ch in enumerate(s):
	start = max(start, pos[ch] + 1)  # ch가 현재 부분문자열의 없는 경우와 있을 때
    max_len = max(max_len, end - start + 1)  # 부분문자열의 최대 길이 갱신
    pos[ch] = end  # ch 문자의 위치 갱신
    
return max_len