[leetcode] 3. Longest Substring Without Repeating Characters

0. 들어가며

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

Longest Substring Without Repeating Characters - LeetCode

 

TCP에서 Window형식으로 슬라이드하면서 움직이면 잡을 수 있나 싶다가, 이걸 iter두 번 도는 식으로 구현해버렸더니 망해버렸다.

N**2 타는게 그렇게 부담되나 싶었는데 케이스를 보고 수긍.

 

 

1. 유의할 테스트케이스

s =" "
# 애매하게 값체크하면 바로 탈락. 

s1 = ""abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ *100
# N**2가 이렇게 나오겠거니.

s2 = "asjrgapa"
# 초기에 2번 탐색하는 방식으로 가니까 a3번 탈때 뭔가 꼬이더라. 큰틀을 이중포인터로 잡고 진행했으면 문제없었을지도?

 

 

2. 망한 코드

def lengthOfLongestSubstring3(self, s):
        print(s)
        window = ""
        domains={}
        for j in range(len(s)):
            
            for idx in range(len(s)-j):
                idx=idx+j
                if window.count(s[idx])==0:
                    window+=s[idx]
                else:
                    temp = len(window)
                    if domains.get(temp) == None:
                        domains.update({temp:window})
                    window = ""+s[idx]
            temp = len(window)
            if domains.get(temp) == None:
                domains.update({temp:window})
            window = ""
        result =list(domains.keys())
        print(domains)
        result.sort()
        if len(result)==0:
            return 0
        return result.pop(-1)

 

지금 생각하면 dictionary좀 잘써봐야지 하고 가져다 붙이긴했는데, sort 태워야 한다던지, 매번 update한다던지도 만만치 않다. 

돌아가는 데모를 만들고 최적화 하는걸 생각했는데, 코스트가 너무 크니 최적화 방향이 빨리 잡히지 않았다.

 

3. 멀쩡한코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        index_map = {}
        start_idx = 0
        max_length = 0    
        for end_idx in range(len(s)):
            if s[end_idx] in index_map and index_map[s[end_idx]] >= start_idx:
                start_idx = index_map[s[end_idx]] +1
            index_map[s[end_idx]] = end_idx
            curr_length = end_idx - start_idx +1
            max_length = max(max_length, curr_length)
        return max_length

 

 

4. 결론

코스트 부터 판단해라 애송이..

Window처럼 프레임을 짜고 슬라이딩하면서 항목을 늘리고 줄이는 코드는 줄곧 보이는것 같다. 

데이터 분석 수준에서는 좀 긴가 민가하네.