슬라이딩 윈도우(sliding window) 기법

• 핵심 아이디어윈도우(Window): 현재 처리 중인 데이터의 범위.
• 윈도우의 크기를 조절하면서 데이터를 순차적으로 탐색.
• 불필요한 데이터를 버리거나 추가하면서 결과 계산.
• 적용 상황부분 배열(또는 문자열) 내 최대/최소 값 찾기예: 길이가 k 인 연속 부분 배열의 최대 합
• 특정 조건을 만족하는 부분 배열 또는 부분 문자열 찾기예: 중복 없는 가장 긴 부분 문자열
• 연속적인 범위 데이터 탐색
• 슬라이딩 윈도우 작동 방식
• 윈도우 시작과 끝을 가리키는 두 포인터를 사용. left는 윈도우의 시작, right는 윈도우의 끝.
• right을 오른쪽으로 이동하여 윈도우를 확장.
• 조건이 만족되지 않으면 left를 이동하여 윈도우를 축소.
• 원하는 조건이 될때까지 반복
• 문제: 주어진 문자열에서 중복 없는 가장 긴 하위 문자열의 길이를 구하라.

def lengthOfLongestSubstring(s: str) -> int:
  char_set = set() # 중복을 확인하기 위한 집합
  left = 0 # 윈도우의 시작점
  max_length = 0 # 결과 값(최대 길이)

  for right in range(len(s)):
    # 윈도우 내에 중복된 문자가 있는 경우, 왼쪽 포인터를 이동하여, 중복 제거
    while s[right] in char_set:
      char_set.remove(s[left]) # 윈도우에서 왼쪽 문자 제거
      left += 1 # 윈도우 시작점 이동
    # 새로운 문자열을 추가하고 최대 길이 갱신
    char_set.add(s[right])
    max_length = max(max_length, right - left + 1) # 현재 윈도우 크기 계산

  return max_length

# 테스트
print(lengthOfLongestSubstring("abcabcbb"))  # 출력: 3 ("abc")
print(lengthOfLongestSubstring("bbbbb"))     # 출력: 1 ("b")
print(lengthOfLongestSubstring("pwwkew"))    # 출력: 3 ("wke")

• 초기 상태:left = 0, right = 0, char_set = {}, max_length = 0
• 윈도우 확장 및 업데이트:right = 0: 문자 “a” 추가 → char_set = {“a”}, max_length = 1
• right = 1: 문자 “b” 추가 → char_set = {“a”, “b”}, max_length = 2
• right = 2: 문자 “c” 추가 → char_set = {“a”, “b”, “c”}, max_length = 3
• 중복 문자 발생 시 윈도우 축소:right = 3: 문자 “a” 중복 → left를 이동해 “a” 제거 → char_set = {“b”, “c”}
• 최대 길이 계산:이후 같은 방식으로 윈도우를 확장 및 축소하여 최대 길이 계산.
• 시간 복잡도O(n): 문자열의 각 문자는 right과 left에 의해 최대 두 번 처리됨.
• 공간복잡도O(k): k는 문자 집합의 크기, 예: 26개 알파벳 또는 전체 문자 집합.
• 슬라이딩 윈도우의 장점:효율적: 불필요한 중복 계산 피함
• 간단구현?: 포인터 2개와 조건만으로 문제 해결

---

아직 어렵네.. https://leetcode.com/problem-list/sliding-window/