[해시] Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters - LeetCode

내 풀이:

def lengthOfLongestSubstring(s):
    if not s:
        return 0
    ans = []
    temp = []
 
    for char in s:
        if char not in temp:
            temp.append(char)
        else:
            ans.append(len(temp))
            start = temp.index(char) + 1
            temp = temp[start:]
            temp.append(char)
 
    # 남아있는 temp 의 길이도 ans 에 추가
    if temp != []:
        ans.append(len(temp))
 
    return max(ans)
 
s = 'dvdf'
# s = 'pwekgeabcdf'
print(lengthOfLongestSubstring(s))

def lengthOfLongestSubstring(s):
    used = dict()
    max_len = start = 0
    for index, char in enumerate(s):
        if char in used and start <= used[char]:
            start = used[char] + 1
        else:
            max_len = max(max_len, index - start + 1)
 
        used[char] = index

---

두 풀이 모두 char의 index를 생각해야 하는 것이 핵심이다.
dict를 사용할 때, value에 index를 넣는 방식을 항상 염두하자.

ex) 같은 'a'가 들어오면 기존에 있던 'a'의 index를 찾아서 index + 1부터 새로운 부분 문자열을 구성한다. 
01234567
abcabcbb
abcabcbb
abcabcbb