[LEET CODE] 3. Longest Substring Without Repeating Characters

# Problem

Given a string s, find the length of the longest substring without repeating characters. Constraints: 0 <= s.length <= 5 * 104 s consists of English letters, digits, symbols and spaces.

 

# My Answer

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s)<=1:
            return len(s)
        sub =[]
        m=0
        for i in range(len(s)):
            for c in s[i:]:
                if c in sub:
                    m = max(m,len(sub))
                    sub=[]
                    break
                else:
                    sub.append(c)
        return max(m,len(sub))

 

# Solution 1 - 슬라이딩 윈도우와 투 포인터로 사이즈 조절

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_length = start = 0
        for index, char in enumerate(s):
            # 이미 등장했던 문자라면 `start` 위치 갱신
            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

used : 현재 문자를 키로 하는 해시 테이블, 현재 위치를 값으로 삽입

하나씩 옮겨가면서 최대 길이 갱신