[3번] Longest Substring Without Repeating Characters

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. deque

2. dict

값이 들어올 때마다 우선 dict에 포함시켜주고 덱에 추가해준다.

이때 만약 dict에 있는 값이 중복으로 들어온다면 덱에 첫번째 값이 중복으로 들어온 값까지 다 빼주고

덱에 가장 왼쪽값을 하나 빼준 후 현재 값을 오른쪽에 추가해준다.

이것을 반복하면 정답을 구할 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

from collections import deque   class Solution:     def lengthOfLongestSubstring(self, s: str) -> int:         cur = 0         ans = 0         dq = deque()         length = len(s)         dic = {}         for i in range(0, length):             if s[i] not in dic:                 dq.append(s[i])                 dic[s[i]] = 1                 cur += 1                 ans = max(ans, cur)             else:                 print(i , s[i])                 while dq and dq[0] != s[i]:                     left = dq.popleft()                     del dic[left]                     cur -= 1                 left = dq.popleft()                 del dic[left]                 cur -= 1                                  dic[s[i]] = 1                 dq.append(s[i])                 cur += 1                 ans = max(ans, cur)                          return ans Colored by Color Scripter

cs