📖 Longest Substring Without Repeating Characters

📖What I thought

• 투포인터 : 시작 위치, 현재 위치 파악

시작 위치 : 중복 문자 발생할 때마다 해당 문자가 마지막으로 발견된 인덱스 + 1로 이동 현재 위치 : 그냥 한 칸 씩 이동하면서 중복문자 체크

• 문자는 문자 & 마지막 발견 인덱스를 저장 → 딕셔너리에 저장하자 (계속 체크해야하므로)
• 딕셔너리에는 {문자:last idx} 형태로 들어가 있음
• 중복 문자인지 아닌지 아는 방법? → 일단 딕셔너리 안에 값이 있으면 중복 → 그리고 last idx가 시작 위치보다 크면(뒤에 있으면) 중복
• 중복 아니면 최대 중복X 길이 갱신

📖풀이

📎Dictionary

class Solution:
    def lengthOfLongestSubstring(self, str: str) -> int:
        hs = dict() # string : index
        st, maxi = 0, 0
    
        for idx, s in enumerate(str):
            # 중복 발생
            if s in hs and hs[s] >= st:
                st = hs[s] + 1
            # 중복 X
            else:
                maxi = max(maxi, idx-st+1)
        
            hs[s] = idx
        
        return maxi

📖What I learned

1. 차근차근 생각한 걸 그대로 코드로 옮기면 다 풀 수 있다
2. 딕셔너리를 잘 활용하자 (ex. {문자:마지막 발견 인덱스}에 저장 → 현재 포인터보다 같거나 크면 중복)

📖관련 지식

📎Hash Table

📎Dictionary