LeetCode 풀기 - 3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

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

Longest Substring Without Repeating Characters - LeetCode

문제)

솔루션1)

Brute-Force로 무식하게 풉니다.

Runtime 시간이 너무 오래걸립니다. 하위 15%.

개선이 필요합니다.

 

# Brute-Force
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        longest_len = 0
        
        for i in range(len(s)):
            temp_len = 1
            for j in range(i + 1, len(s)):
                if s[j] in s[i:j]:
                    break
                temp_len += 1
            longest_len = max(temp_len, longest_len)
        return longest_len

솔루션2)

중복된 연산을 최대한 줄이고자 슬라이딩 윈도우 방식을 적용합니다.

직관적이고 구현이 쉽습니다.

Runtime 시간이 70%에 드네요.

 

window에서 원소를 삭제하는 연산의 오버헤드가 있습니다.

좀 더 개선의 여지가 있네요.

# Sliding-window
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window = []
        l = 0
        res = 0
        
        for r in range(len(s)):
            while s[r] in window:
                window.remove(s[l])
                l += 1
            window.append(s[r])
            res = max(res, len(window))
        return res

솔루션3)

hash 자료구조를 사용합니다.

Runtime 속도 93%입니다.

 

시간 복잡도 : O(N)

공간 복잡도 : O(N)

 

# hash
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start = 0
        max_len = 0
        seen = {}

        for i, c in enumerate(s):
            if c in seen and start <= seen[c]:
                start = seen[c] + 1
            else:
                max_len = max(max_len, i - start + 1)
            seen[c] = i
        return max_len