[LeetCode] Longest Substring Without Repeating Characters

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

Longest Substring Without Repeating Characters - LeetCode

중복없는 가장 긴 증가하는 부분수열 문제

투 포인터와 dict 자료구조를 활용하면 된다.

 

예전 풀이

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        longest = left = right = 0
        string_set = set()
        while right < len(s):
            if s[right] in string_set:
                longest = max(len(string_set), longest)
                while left < right:
                    if s[left] == s[right]:
                        left += 1
                        break
                    else:
                        string_set.remove(s[left])
                        left += 1
            else:
                string_set.add(s[right])
            right += 1
        return max(longest, len(string_set))

 

깔끔한 풀이

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_length = start = 0
        for index, char in enumerate(s):
            if char in used and start <= used[char]:
                start = used[char] + 1
            else:
                max_length = max(max_length, index - start + 1)
                
            used[char] = index
            
        return max_length