[LeetCode] 3. Longest Substring Without Repeating Characters

🔦 문제 링크

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

• 문제

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

✍️ 풀이

---

슬라이딩 윈도우와 투포인터의 개념을 이용하는 문제.

먼저 문자열이 중복되지 않을 때까지 부분문자열을 추가한다.
만약, 중복된 문자를 만나면 무시한다. 이렇게 마지막 문자까지 검사를 했을 때 최대 길이가 정답이 된다.

두번째 방법은 위 방법을 좀 더 개선한 방법이다.
똑같이 중복된 문자를 만날 때 까지 부분 문자열을 추가한다.
중복된 문자를 만나면 중복된 문자의 인덱스 뒤를 부분 문자열 시작지점으로 잡는다.
이 때 주의해야하는 점은 시작지점이 이미 중복 문자지점을 넘어갔다면 새롭게 길이를 갱신해줘야만 한다.

🛠 코드

---

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
                

---

📝 정리

---

🎈 참고

---

Book 링크