[LeetCode][Python3] 3. Longest Substring Without Repeating Characters

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