[Leetcode 3] Longest Substring Without Repeating Characters

# medium

 

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

 

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

 

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

 

무지성 풀이

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        mem = []
        cnt = 0
        answer = 0
        for c in s:
            if c not in mem:
                cnt += 1
                mem.append(c)
            else:
                answer = max(answer, cnt)
                cnt = 1
                mem = [c]
        answer = max(answer, cnt)
        return answer

ㅎㅎ.. 그냥 무지성으로 로직 세우고 푼 코드.

앞에서 하나씩, 그냥 한 방향으로 진행한 것이다.

dvdf의 경우 이 로직상에선 vdf를 찾지 못하고 dv, df만 확인한다.

 

Sliding Window

중복을 포함하지 않는 substring 중 가장 긴 것. 다시 말하면 substring 내에 어떤 알파벳이 한 번만 들어있어야 한다는 것이다.

 

알파벳의 갯수는 유한하니까, 각 알파벳별로 최근에 등장한 index를 저장하고

동일한 글자가 나오면 최근에 등장했던 index의 다음 index부터 substring을 시작하면 된다.

dvdf라고 하면, 두 번째  d를 만났을 때 최근 d의 index가 0이었기 때문에 1번 index부터 다시 substring을 만든다고 생각하고 길이를 재는 방법으로 생각했다.

	a	b	c	d	e	b	a	c	e
	1	1	1	1	1	@
		@	2	2	2	2	2	#
			#	3	3	3	3	3	%
					%	4	4	4	4

이렇게 진행되어야 한다. substring의 시작점이 방금 만난 알파벳의 바로 다음 index이다.

1번 substring을 진행할 때 { a:0, b:1, c:2, d:3, e:4, f:-1, ... }이다.

이후 { a:0, b:5, c:2, d:3, e:4, f:-1, ... } 이렇게 업데이트하고 2번 substring을 시작할 땐 a는 아직 등장하지 않은 상태이다.

따라서 원래 b인덱스였던 1보다 큰 인덱스에 있는 글자들이 또 나오는 경우만 경계하면 된다.

 

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        mem = defaultdict(lambda: -1)
        length = 0
        answer = 0
        substring_start = -1		# 지금 확인하는 substring 구간에서 중복이 없으면 된다
        for i, c in enumerate(s):
            if mem[c] > substring_start:
                answer = max(length, answer)
                length = i-mem[c]
                substring_start = mem[c]
            else:
                length += 1
            mem[c] = i
        answer = max(length, answer)
        return answer

 

처음 확인하는 substring은 0부터니까. mem[c]에 0이상인 값이 있다는 건 지금 확인하는 substring안에 이미 글자가 들어있다는 의미.

 

sliding window 알고는 있었는데 그걸 적용해야지 한 건 아니고, 중복되는 계산 안하려다보니까 결국은 sliding window를 활용한 셈이 되어버렸는데, 이걸 알고 반영하면 코드가 더 깔끔해진다.

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        ans = 0
        left_cursor = 0     # substring의 시작점
        used = {}
        for right_cursor, char in enumerate(s):
            if char in used and left_cursor <= used[char]:
                left_cursor = used[char] + 1    # 지금 겹친 글자의 다음 글자부터 새로운 substring 시작점 설정
            else:
                ans = max(ans, right_cursor - left_cursor + 1)
            used[char] = right_cursor
        return ans

 

복잡도

Time - O(N)

Space - O('z'-'a') 알파벳 갯수만큼의 list와 변수 몇 개.

 

Runtime: 49 ms, faster than 87.48% of Python online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 13.4 MB, less than 95.67% of Python online submissions for Longest Substring Without Repeating Characters.

 

코드 깔끔하게 한 게 약간 더 빠르다. 쓸 데 없이 딕셔너리 초기화하는 짓을 안해서 그런건지...

 

참고 사이트

https://www.daleseo.com/python-collections-defaultdict/

[파이썬] 사전의 기본값 처리 (dict.setdefault / collections.defaultdict)

→ dictinary 기본 값으로 세팅하기

 

https://velog.io/@zwon/%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0Sliding-Window

Sliding Window