Sliding Window와 HashSet 기반 O(N) 시간 복잡도 달성

Context

중복 문자가 없는 최장 부분 문자열을 찾는 문제로, 모든 부분 문자열을 전수 조사하는 Brute-force 방식 채택 시 O(N^2)의 시간 복잡도 발생. 연속된 구간을 효율적으로 탐색하며 중복을 제거하는 최적화된 윈도우 관리 구조 필요.

Technical Solution

• Two Pointers 기반의 Sliding Window 구조를 설계하여 탐색 범위의 불필요한 중복 계산 제거
• HashSet을 통한 현재 윈도우 내 문자 존재 여부를 O(1) 시간 복잡도로 확인하는 메커니즘 구현
• Right Pointer를 통한 윈도우 확장을 기본 전략으로 설정하여 입력 문자열 전체를 1회 순회
• 중복 문자 발견 시 Left Pointer를 이동시켜 중복 요소가 제거될 때까지 윈도우 크기를 축소하는 동적 제어 로직 적용
• 매 단계에서 (Right - Left + 1) 수식을 통해 현재 유효한 최장 길이를 갱신하는 상태 관리 수행