3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

 

https://youtu.be/wiGpQwVHdE0?si=b-6NK2xTHLhlVE5-

 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 중복되지 않은 문자를 저장할 집합 (현재 윈도우의 문자들)
        charSet = set()

        # 윈도우의 왼쪽 포인터
        l = 0

        # 결과값(최대 길이)을 저장할 변수
        res = 0

        # 윈도우의 오른쪽 포인터를 문자열의 각 문자에 대해 순회
        for r in range(len(s)):
            # s[r]이 이미 charSet에 존재한다면, 중복된 문자를 제거하기 위해 윈도우를 축소
            while s[r] in charSet:
                charSet.remove(s[l])  # 윈도우의 왼쪽 끝 문자를 제거
                l += 1  # 왼쪽 포인터를 오른쪽으로 이동
            
            # s[r]을 charSet에 추가 (현재 문자 포함)
            charSet.add(s[r])

            # 현재 윈도우의 길이를 계산하고 최대 길이(res)와 비교하여 갱신
            res = max(res, r - l + 1)

        # 최대 길이를 반환
        return res

 

코드 설명

1. 문자 집합 (charSet):
   • 현재 윈도우에 포함된 중복되지 않은 문자들을 저장합니다.
   • 집합(set)을 사용하면 특정 문자가 이미 포함되어 있는지 확인하는 작업이 O(1)의 시간 복잡도로 가능.
2. 왼쪽 포인터(l):
   • 슬라이딩 윈도우의 왼쪽 끝을 나타냅니다.
   • 중복 문자가 발견되면 l을 오른쪽으로 이동시켜 윈도우를 축소.
3. 오른쪽 포인터(r):
   • 슬라이딩 윈도우의 오른쪽 끝을 나타냅니다.
   • r이 순회하며 윈도우를 확장합니다.
4. 현재 윈도우의 길이 계산:
   • 윈도우의 길이는 r - l + 1로 계산.
   • 매번 계산한 길이와 res(최대 길이)를 비교하여 갱신.
5. 중복 제거:
   • while s[r] in charSet 조건을 통해 s[r]이 이미 집합에 있는 경우를 처리.
   • 중복을 제거하기 위해 s[l]을 charSet에서 제거하고, l을 증가시켜 윈도우 축소.

동작 과정 예제

 

시간 복잡도

• O(n):
  • r은 문자열을 순회하며 한 번씩만 증가.
  • l도 필요할 때만 이동하며 문자열을 순회.
  • 따라서 전체 시간 복잡도는 O(n).

공간 복잡도

• O(k):
  • k는 중복 없는 문자 집합의 최대 크기.
  • 집합 charSet에 최대 O(k) 공간 사용.

 

https://youtu.be/ZqG_sk9AS44?si=v-dl6h3hMGx8RuLb

 

이 코드가 더 이해 감!!

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 결과 값: 가장 긴 부분 문자열의 길이를 저장할 변수
        maxLen = 0

        # 현재 윈도우 내의 중복되지 않은 문자들을 저장할 집합
        chars = set()

        # 슬라이딩 윈도우의 왼쪽(l)과 오른쪽(r) 포인터 초기화
        l, r = 0, 0

        # 오른쪽 포인터(r)가 문자열 s의 끝에 도달할 때까지 반복
        while r < len(s):
            # 현재 문자가 집합(chars)에 이미 포함되어 있는지 확인
            if s[r] in chars:
                # 중복된 문자가 있는 경우:
                # 윈도우의 왼쪽 끝 문자(s[l])를 집합에서 제거하고
                chars.remove(s[l])
                # 왼쪽 포인터를 오른쪽으로 한 칸 이동
                l += 1
            else:
                # 중복된 문자가 없는 경우:
                # 현재 문자를 집합에 추가
                chars.add(s[r])
                # 오른쪽 포인터를 오른쪽으로 한 칸 이동
                r += 1
                # 현재 윈도우의 길이(r - l)와 기존 maxLen을 비교하여 최대값 갱신
                maxLen = max(r - l, maxLen)

        # 가장 긴 부분 문자열의 길이 반환
        return maxLen

 

https://youtu.be/qJKKBCHzRKE?si=3Gf5GswV1WGRebq-