[LeetCode] #3. Longest Substring Without Repeating Characters (HashMap, Medium)

[Cheolsker]

제한사항

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols and spaces.

아이디어

1. 문자별로 사이즈를 하나씩 키워가며, 가장 큰 중복없는 문자열 찾기 ( O(N^2 ) - 시간 초과
   a. s.length < 2 인경우 s.length 리턴 ( 0 또는 1 리턴)
   b. size 는 2부터 시작
   c. size <= s.length 인 경우 계속 반복하고, 반복문 시작 시, idx=0 리셋, 반복문 끝에 size++
   d. 내부에 idx+size <= s.length 인 경우 반복,
   e. 내부 반복문에서, subStr = s.slice(idx, idx+size), set = new Set(subStr)
   f. subStr.length == set.size 이면, maxLength에 subStr.size 갱신�하고 내부 반복문 종료 (break)
   g. f 조건을 만족하지 못하면, idx++ 하고 내부 반복문 계속 실행
   h. 최종 maxLength를 반환

2. 해시맵과 슬라이딩 윈도우를 이용해서 문제해결 ( O(N) )
   a. 문자열 길이만큼 반복, O(N)
   b. 이미 등장한 문자이고, 슬라이딩 윈도우 안쪽에 있다면 left 업데이트
   c. b에 해당하지 않으면, 최대 문자길이 업데이트
   d. 매 반복문 끝에, 현재문자 위치 삽입 (map.set(c, right)) + 오른쪽 포인터는 현재문자 위치에 맞게 계속 증가 (right++)