[LeetCode] 3. Longest Substring Without Repeating Characters

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

문자열 s가 주어지면 반복되는 문자없이 가장 긴 부분 문자열의 길이를 찾습니다.

✍️ 풀이

---

가능한 모든 부분 문자열을 비교해보는 브루트포스 방식을 시도 했지만 시간 초과가 발생했다.

이 문제는 시간 복잡도 O(n)에 해결해하기위해 슬라이딩 윈도우와 투 포인터를 활용해야 한다.

슬라이딩 윈도우는 보통 정렬되지 않은 데이터에 고정 크기 윈도우를 통해 사용하고 투 포인터는 정렬된 데이터에 가변 크기 윈도우를 사용한다.

• 문제 해결 과정

1. 이 문제는 중복되는 문자가 발견될 때는 중복되는 문자의 위치와 현재 시작위치를 비교한다. 만약 중복되는 위치가 더 크다면 새로운 시작 위치가 된다.

2. 만약, 한번도 발견되지 않은 문자라면 문자 하나가 추가되었으므로 현재 - 시작 + 1 한 길이와 최대 길이를 비교해 갱신한다.

3. 매 반복마다 항상 해야하는 일은 문자에 따른 위치를 갱신하는 것이다.
   이것은 문자가 중복이 되었든 처음 발견이든 항상 위치 값 갱신을 수행한다.

🛠 코드

---

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 슬라이딩 윈도우와 투포인터
        used = dict()
        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

---

📝 정리

---

하나 주의 해야할 점은 if char in dic 조건 대신 if dic.get(char) 조건을 사용하면 안된다.
왜냐하면 딕셔너리의 값으로 인덱스 0이 가능하기 때문에 조건이 의도한대로 동작하지 않는다.

🎈 참고

---

Book 링크