Problem :

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


My Solution :

class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
ans = 0
substring = set()
i = j = 0
while j < len(s):
if s[j] not in substring:
substring.add(s[j])
j += 1
ans = max(ans, j-i)
else:
substring.discard(s[i])
i += 1
return ans


Comment :

위 방법은 set을 이용해 직접 substring을 유지하면서 i, j를 움직여 구하는 방법. 아래는 dictionary를 이용해 마지막 중복된 문자 인덱스를 기록하며 구하는 방법.


My Solution2 :

class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
ans = last_unique = 0
last_index = {}
for i, c in enumerate(s):
if c in last_index:
last_unique = max(last_unique, last_index[c] + 1)
ans = max(ans, i - last_unique + 1)
last_index[c] = i
return ans