Algorithm | Longest Substring Without Repeating Characters

본 글은 leetCode의 Longest Substring Without Repeating Characters 문제 솔루션을 JavaScript 코드로 정리한 글입니다.

Approach 2: Sliding Window

문자열에 두 개의 index가 순회하며 substring의 시작과 끝을 가리킵니다. 끝을 가리키는 인덱스가 반복되는 문자를 발견하면 시작을 가리키는 인덱스를 반복된 문자가 없을 때까지 한 칸 씩 앞으로 이동합니다.

var lengthOfLongestSubstring = function(s) {
  let max = 0;
  let i = 0;
  let j = 0;
  let set = {};
  while(i < s.length && j < s.length) {
    if(set[s[j]]) {
      delete set[s[i++]];
    } else {
      set[s[j++]] = true;
      max = Math.max(max, j - i);
    }
  }
  return max;
};

시간복잡도

O(N)

최악의 경우, 에를 들어 aaaaaa와 같은 경우, i와 j가 한 번씩 지나갑니다. abcdef와 같은 최선의 경우에선 i는 while이 종료될 때까지 i = 0 그대로이고, j만 문자열을 한 번 순회합니다. 최악의 경우엔 반복문이 2n번, 최선의 경우엔 n번 반복하기 때문에 시간복잡도는 O(N)입니다.

Approach 3: Sliding Window Optimized

위의 방법을 좀 더 최적화하여 반복문을 n번만 반복하도록 하는 방법입니다.

이전에는 substring의 끝위치인 j에 재등장하는 문자가 있다면 i를 하나씩 증가하면서 중복된 문자 다음 위치로 이동할 때까지 기다렸습니다.

하지만 이번에는 i를 하나씩 올리지 않고 바로 중복된 문자 다음으로 이동시킵니다.

var lengthOfLongestSubstring = function(s) {
  let max = 0;
  let hash = {};
  for(let i = 0, j = 0; j < s.length; ++j) {
    if(hash[s[j]] !== undefined)
      i = Math.max(i, hash[s[j]] + 1);
    hash[s[j]] = j;
    max = Math.max(max, j - i + 1);
  }
  return max;
};

시간복잡도

O(N)

References

https://leetcode.com/problems/longest-substring-without-repeating-characters/solution/

Back to top ↑