Longest Substring Without Duplication

알고리즘 - 해시
이유 - 각각의 캐릭터에 해당하는 인덱스 넘버가 필요하다 (캐릭터:인덱스)
TODO: longest substring 언제 업데이트 해야하는지, duplicate 발견했을때 어떻게 다루어야 하는지(새로 시작하려면 시작포인터를 업데이트 해야하는지, 한다면 항상 해야하는건지 등)

# s       p                     
# c l e m e c n t i s a c a p 
# 0 1 2 3 4 5 

def longestSubstringWithoutDuplication(string):
    if len(string) == 0:
        return 0 
    start = 0
    longest = '' 
    map = {}
    
    for index, char in enumerate(string):
        if char in map: 
            if map[char] >= start:
                if len(longest) < index - start:
                    longest = string[start: index]
                start = map[char] + 1
        map[char] = index
        if len(longest) < index - start +1: 
            longest = string[start: index+1] 
    return longest 

#when - currentLongest < endPtr - start 
longest = clem #(string[start:endPtr]) string[0:5] 0~4 

#when - already in map and its index in between start and end, meaning bigger than start 
start = m~ (e+1) #map[char] +1 

#for loop 
map[char] = index #for loop 

#for every character 
if len(longest) < index - start +1: 
            longest = string[start: index+1] 
            

처음 인터뷰 연습할때 처음 알고리즘 오르는것부터 풀기까지 1시간 45분 걸렸었다 (105분) 그닥 어려운 문제는 아닌데 긴장해서 그런지 아는데도 해맸다. 인터뷰때는 시간이 빠르게 가는것 같다. 연습으로 충당하자.