3. Longest Substring Without Repeating Characters

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

My Answer 1: Accepted (Runtime: 1696 ms - 5.01% / Memory Usage: 14.5 MB - 6.29%)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 1:
            return 1

        longest = 0
        
        for j in range(len(s)):
            result = [s[j]]
            for i in range(j+1, len(s)):
                if s[i] not in result:
                    result.append(s[i])
                else:
                    break
            longest = max(longest, len(result))
        
        return longest

why... ㅎ6상 2中 for 곰ㅇi.. LㅓbooEㅓ 생각..ㄴr는girlㄱㄱㅏ...☆★

비효율의 끝판왕 모셨읍니다.

각 문자를 시작으로 하는 모든 substring without repeating 을 구해서 max 값 찾기

My Answer 2: Accepted (Runtime: 124 ms - 23.27% / Memory Usage: 14.3 MB - 82.30%)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 1:
            return 1
        
        result = []
        longest = 0
        
        for i in range(len(s)):
            if s[i] not in result:
                result.append(s[i])
            else:
                while s[i] in result:
                    result.pop(0)
                result.append(s[i])
            longest = max(longest, len(result))
        
        return longest

이번에는 반복되는 값이 있으면 result 에서 pop 해주는 식으로 함

My Answer 3: Accepted (Runtime: 72 ms - 50.51% / Memory Usage: 14.1 MB - 94.12%)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 1:
            return 1
        
        result = []
        longest = 0
        
        for i in range(len(s)):
            if s[i] not in result:
                result.append(s[i])
            else:
                result = result[result.index(s[i])+1:]
                result.append(s[i])
            longest = max(longest, len(result))
        
        return longest

2 번째 답이랑 같지만 while 문으로 pop 하는 대신 index 값을 이용해서 자른 버전..

어느새 런타임 5% 에서 50% 되다...!

뭔가 해시 이용해도 좋을 거 같음

Slide window with dictionary

Solution 1: Runtime: 60 ms - 78.06% / Memory Usage: 14.3 MB - 82.30%

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
        left = -1
        res = 0        
        for i in range(len(s)):
            if s[i] in dic and dic[s[i]] > left:
                left = dic[s[i]]
            dic[s[i]] = i
            res = max(res, i-left)
        return res

딕셔너리를 이용한 솔루션

dic 에는 [값:인덱스] 형식으로 저장하고 left 변수에 substring 시작 인덱스 값이 들어감