LeetCode [3]: Longest Substring Without Repeating Characters

📌 LeetCode [3]: Longest Substring Without Repeating Characters

🔗 문제 링크

---

문제 설명 📄

문자열 ( s )가 주어졌을 때, 중복되지 않은 문자로만 이루어진 가장 긴 부분 문자열의 길이를 반환하는 문제입니다.

---

문제 접근 방식 📋

1. 슬라이딩 윈도우와 deque 활용:
   • 중복 문자가 발견될 때까지 앞쪽 문자들을 제거하며, 중복이 없도록 유지합니다.
   • deque는 현재 윈도우의 문자들을 저장하며, set은 중복 검사를 위해 사용합니다.
2. 반복문으로 윈도우 탐색:
   • 문자열의 각 문자를 순회하며, 중복이 발생하면 deque의 앞쪽 문자를 제거합니다.
   • 매 단계마다 현재 윈도우의 길이를 갱신합니다.
3. 최대 길이 반환:
   • 탐색이 끝난 후 최대 길이를 반환합니다.

---

Solution 💻

from collections import deque

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        maxLen = 0
        q = deque()
        pattern = set()

        for i in range(len(s)):
            if s[i] in pattern:
                maxLen = max(maxLen, len(q))
                while q:
                    poped = q.popleft()
                    pattern.remove(poped)
                    if poped == s[i]:
                        break

            q.append(s[i])
            pattern.add(s[i])

        maxLen = max(maxLen, len(q))

        return maxLen

시간 복잡도 분석 ⏲️

• 시간 복잡도: (O(n))
  • 문자열 (s)의 길이가 (n)일 때, 각 문자는 최대 두 번씩 처리됩니다(한 번 추가, 한 번 제거).
• 공간 복잡도: (O(n))
  • deque와 set을 사용하여 최대 (n)개의 문자를 저장.

---

리팩토링 🛠️

개선된 코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        maxLen = 0
        start = 0
        pattern = {}

        for end in range(len(s)):
            if s[end] in pattern and pattern[s[end]] >= start:
                start = pattern[s[end]] + 1

            pattern[s[end]] = end
            maxLen = max(maxLen, end - start + 1)

        return maxLen

리팩토링 후 시간 복잡도 ⏲️

• 시간 복잡도: (O(n))
  • 각 문자는 딱 한 번씩 순회 및 처리됩니다.
• 공간 복잡도: (O(n))
  • pattern 딕셔너리로 최대 (n)개의 문자를 저장.

차이점:

• deque를 사용하지 않고, 인덱스 기반 접근으로 구현.
• start 변수를 사용하여 중복을 건너뛰는 방식으로 탐색 효율성을 증가.