Sliding Window와 Set을 활용한 O(n) 시간 복잡도 달성

Context

중복 문자 없는 가장 긴 부분 문자열을 찾기 위해 전체 문자열을 탐색해야 하는 상황. 모든 부분 문자열을 전수 조사하는 방식은 시간 복잡도가 과도하게 증가하는 한계 존재.

Technical Solution

• 중복 발생 시 윈도우를 처음부터 재시작하는 대신 Left Pointer를 이동시키는 Sliding Window 전략 채택
• 윈도우 내 문자 존재 여부를 O(1) 시간으로 확인하기 위해 Hash Set 기반의 Guest List 구조 설계
• Right Pointer로 윈도우를 확장하며 새로운 문자를 추가하는 선행 동작 구현
• 중복 문자 발견 시 해당 문자가 제거될 때까지 Left Pointer를 전진시키며 Set에서 요소를 삭제하는 축소 로직 적용
• 매 단계에서 Right - Left + 1 연산을 통해 현재 윈도우 크기를 계산하고 Global Max 값 갱신
• 모든 문자가 Set에 한 번 진입하고 한 번 퇴출되는 구조를 통해 불필요한 Backtracking 제거