3. Longest Substring Without Repeating Characters (Hash Table, String, Sliding Window)

링크 - https://leetcode.com/problems/longest-substring-without-repeating-characters/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) Straightforward Sliding Window

1. 먼저 hash_table를 만든다. 이것은 각 글자에 대한 인덱스를 저장하기 위함이다.

2. right를 len(s)만큼 for문으로 돌린다. 그리고 s[right]가 hash_table에 없으면 글자와 인덱스를 해시테이블에 넣고 ans를 업데이트한 뒤, 진행한다.

3. 만약 s[right]가 hash_table에 있다면, 우리는 중복된 글자가 있으므로 left를 통해 s[right]와 같은 글자가 나올때까지 hash_table를 지우면서 움직인다. 만약 left != right이면, left는 중복된 글자를 가리키고 있으므로 이를 제거 후 하나 더 이동시킨다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0

        hash_table = {}
        left = 0
        for right in range(len(s)):
            if s[right] not in hash_table:
                hash_table[s[right]] = right
            else:
                while s[left] != s[right]:
                    del hash_table[s[left]]
                    left += 1
                if left != right:
                    del hash_table[s[left]]
                    left += 1
                hash_table[s[right]] = right
            ans = max(ans, right - left + 1)

        return ans

Time Complexity: O(2n)

Space Complexity: O(min(m, n)) 여기서 n은 s의 글자 개수이고, m은 s가 가지고 있는 unique 글자 개수이다.

2) Optimized Sliding Window

우리는 굳이 while문을 사용하여 left를 움직이지 않아도 된다. hash_table에 right+1의 인덱스를 저장해서 매번 s[right]가 hash_table에 있는 것을 확인하고 난 뒤, max(hash_table[s[right]], left)을 통해 left를 이동시키면 된다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        ans = 0
        # charToNextIndex stores the index after current character
        hash_table = {}

        left = 0
        for right in range(n):
            if s[right] in hash_table:
                left = max(hash_table[s[right]], left)

            ans = max(ans, right - left + 1)
            hash_table[s[right]] = right + 1

        return ans

Time Complexity: O(n)

Space Complexity: O(min(m, n)) 여기서 n은 s의 글자 개수이고, m은 s가 가지고 있는 unique 글자 개수이다.