3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

문제

주어진 문자열에서 중복되지 않는 가장 긴 부분 문자열의 길이를 반환한다. 테스트 케이스 문자열 "pwwkew"에는 조건을 충족하는 substring으로 "wke", "kew", 즉 length는 3이 된다. 햇갈릴 수 있는 부분 수열(subsequence)가 아니라 부분 문자열(substring)은 연속된 문자열이라는 점이 다르다.

테스트 케이스

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, 
"pwke" is a subsequence and not a substring.

풀이

슬라이딩 윈도우(Sliding Window) 알고리즘

슬라이딩 윈도우란, 고정된 크기의 윈도우를 이동시키면서 필요한 정보를 갱신하는 알고리즘이다. 배열 요소의 일정 범위의 연속된 값을 비교할 때 유용하다. start(left), end(rigth)인 두 포인터를 이용해 마치 창문을 여는 것처럼, 범위를 변경하면서 윈도우 크기를 조절하는 문제에 적합하다.

윈도우의 시작과 끝을 나타내는 두 포인터 left와 right 변수를 사용한다. Set()을 사용하여 문자열을 저장하고, 현재 저장된 문자열의 수와 maxLen(이전에 저장된 문자열 길이) 중 큰 수로 업데이트한다. 중복된 문자가 나타나면 left 포인터의 인덱스를 증가시켜서 윈도우 범위를 조정한다. right 포인터가 문자열을 순회할 때까지 반복한다. 시간 복잡도는 O(n)이 된다.

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  let left = 0, right = 0, maxLen = 0;
  let map = new Set();

  while (right < s.length) {
    if (!map.has(s[right])) {
      map.add(s[right]);
      right++;
      maxLen = Math.max(maxLen, map.size)
    } else {
      map.delete(s[left]);
      left++
    }
  }
  return maxLen
};