Leetcode - 3. Longest Substring Without Repeating Characters

문제

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

풀이

처음에는 2중 루프로 풀었다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        record = 0
        for i in range(len(s)):
            for j in range(i, len(s)):
                substring = s[i:j+1]
                if len(substring) == len(set(substring)):                                  
                    record = max(record, len(substring))
                else:
                    break
        return record

별 생각 없이 모든 경우의 수를 다 따지면 쉽게 풀 수 있다. 다만 시간복잡도가 $O(nlogn)$, 최악의 경우 $O(n^2)$이 된다.

투 포인터로 풀면 더 간단하다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        head = -1
        record = 0
        
        for idx, char in enumerate(s):
            if char in used and head <= used[char]:
                head = used[char]
            else:
                record = max(record, idx - head)
            used[char] = idx
            
        return record

다만 중복된 문자를 받을 경우 head를 어디에 둬야하는지 생각을 잘 해야 한다.