[Sliding Window Variable Size] 3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

 

최종 코드

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

 

이 문제는 슬라이딩 윈도우 기법을 사용해서 효율적으로 풀 수 있어요.
핵심 아이디어는: 중복 문자가 없을 때까지 윈도우를 오른쪽으로 확장하고,
중복 문자가 나오면 왼쪽 포인터를 이동시켜 중복을 제거하는 거예요.

 

🧠 예제 설명

예제 1: "zxyzxyz"

• "zxy" (길이 3)까지는 중복 없음 → 계속 확장
• "zxyz"에서 다시 'z' 중복 → "xyz"부터 다시 시작
• 가장 긴 중복 없는 부분은 "xyz" → 정답: 3

---

✅ 시간복잡도

• O(n) (n은 문자열 길이)
• 각 문자는 최대 한 번씩 set에서 추가/제거됨

 

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-

 

다시..여기서..이해가 감

✅ 문제 요약:

중복 문자가 없는 가장 긴 부분 문자열의 길이를 구하는 문제입니다.

• **부분 문자열(substring)**은 문자열 내 연속된 문자들의 집합입니다.
• 중복이 없는 가장 긴 구간의 길이를 반환하면 됩니다.

---

✅ 예시 설명

예시 1:

입력: "zxyzxyz"

• 가능한 중복 없는 구간: "zxy", "xyz", "yzx", "zxy" 등
• 이 중에서 가장 긴 건 "zxy" 혹은 "xyz" → 길이 3

---

예시 2:

text

복사편집

입력: "xxxx"

• 같은 문자만 반복 → "x" 한 글자만 가능 → 길이 1

---

✅ 제약 조건

• 문자열의 길이는 최대 1000자
• 공백 포함한 모든 ASCII 문자 가능

---

✅ 핵심 아이디어

슬라이딩 윈도우 + 해시셋(set) 사용

1. 왼쪽 포인터 start와 오른쪽 포인터 end로 창(window)을 만들고,
2. 문자를 하나씩 보면서 중복이 없는지 확인
3. 중복이 있으면 start를 앞으로 이동 => left 를 오른쪽으로 증가
4. 중복이 없으면 창의 길이를 업데이트 => right를 오른쪽으로 증가

def lengthOfLongestSubstring(s: str) -> int:
    seen = set()  # 중복 없이 현재 부분 문자열에 포함된 문자들을 저장하는 집합
    left = 0      # 부분 문자열의 시작 인덱스 (슬라이딩 윈도우의 왼쪽 끝)
    max_len = 0   # 지금까지 찾은 가장 긴 중복 없는 부분 문자열의 길이

    # 문자열의 각 문자를 오른쪽 끝(right)으로 순회
    for right in range(len(s)):
        # 현재 문자가 seen 집합에 이미 있다면 → 중복 발생
        while s[right] in seen:
            # 왼쪽 문자를 집합에서 제거하면서 왼쪽 포인터를 한 칸 앞으로 이동
            seen.remove(s[left])
            left += 1
        
        # 중복이 없어진 상태이므로 현재 문자를 seen에 추가
        seen.add(s[right])

        # 현재 윈도우 길이 = 오른쪽 인덱스 - 왼쪽 인덱스 + 1
        # 최댓값 갱신
        max_len = max(max_len, right - left + 1)

    # 최종적으로 가장 길었던 중복 없는 부분 문자열의 길이 반환
    return max_len