[파이썬 알고리즘] 11장 - 중복문자 없는 가장 긴 부분 문자열 (leetcode 3) ⭐

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

 

<문제>

중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라

 

<예시>

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

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

 

---

1. 덜 최적화된 코드

# my solution
# (runtime 148ms) faster than 21% / (memory 14.3MB) less than 64%
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        right = 1
        max_value = 0

        while right != len(s)+1:
            unique_alpha = set(s[left:right])
            if len(unique_alpha) == right-left:
               max_value = right-left if right-left > max_value else max_value
               right += 1
            else:
                left += 1
                right += 1
        return max_value

 

 

2. 더 최적화된 코드

class Solution2:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_length = 0
        start = 0

        for index, char in enumerate(s):
            if char in used and start <= used[char]:
                # 기존에 나왔던 적이 있고 AND 이 글자가 현재 구간에 포함되면!
                start = used[char]+1
            else:
                # 기존에 나왔던 적이 없거나 OR 이 글자가 현재 구간에 포함되지 않으면!
                max_length = max(max_length, index-start+1)
            used[char] = index  # 나온 위치를 기록
        return max_length

 

index = 0

0	1	2	3	4	5	6	7	8	9
a	b	a	a	c	b	e	b	f	g

start = 0

max_length = 1

 

 

index = 1

0	1	2	3	4	5	6	7	8	9
a	b	a	a	c	b	e	b	f	g

start = 0

max_length = 2

 

index = 2

0	1	2	3	4	5	6	7	8	9
a	b	a	a	c	b	e	b	f	g

start = 1

max_length = 2

 

 

index = 3

0	1	2	3	4	5	6	7	8	9
a	b	a	a	c	b	e	b	f	g

start = 3

max_length = 2

 

...

index = 7

0	1	2	3	4	5	6	7	8	9
a	b	a	a	c	b	e	b	f	g

start = 3 -> 6 ⭐이것이 성능 향상의 포인트!!!

max_length = 4

 

 

+) KMP와 비슷한 아이디어 사용하는 것 같다!