[알고리즘 JS] Sliding window - 중복이 없는 가장 긴 문자열의 길이 찾기

주어진 문자열에서 중복이 없는 가장 긴 길이를 구하는 문제이다. 

처음에는 부분 문자열을 매번 구하고 해당 부분 문자열에 현재 문자열이 존재하는지를 찾는 방법이 떠올랐다.

이 경우 시간 복잡도가 O(n^2) 이므로 상당히 비효율적이다.

이 때 슬라이딩 윈도우 기법을 사용하면 문자열 길이만큼 반복하여 O(n) 의 선형 시간 복잡도로 문제를 해결할 수 있다. 

[findLongestSubstring]

Write a function called findLongestSubstring, which accepts a string and returns the length of the longest substring with all distinct characters.

ex)
  findLongestSubstring(''), // 0 
findLongestSubstring('rithmschool'), // 7 
findLongestSubstring('thisisawesome'), // 6 
findLongestSubstring('thecatinthehat'), // 7 
findLongestSubstring('bbbbbb'), // 1 
findLongestSubstring('longestsubstring'), // 8 
findLongestSubstring('thisishowwedoit'), // 6

출처 : Udemy JavaScript 알고리즘 & 자료구조 마스터클래스

솔루션을 보지 않은 나의 첫 풀이는 아래와 같다. 

0부터 시작해서 각 문자열을 key 값으로 갯수를 계속 카운트했다.

카운트하는 도중 갯수가 2 이상이 되면 중복 문자열이기 때문에, 현재까지의 길이를 Max 값으로 저장하고,

윈도우 범위를 좁혀가며 길이를 구했다.

function findLongestSubstring(str) {
  let map = {};

  let start = 0;
  let end = 0;
  let maxLen = 0;

  while (start < str.length && end < str.length) {
    const key = str[end];

    // key 값이 없는 경우 추가하고 end 증가
    if (!map[key]) {
      map[key] = 1;
      end++;
      maxLen = Math.max(maxLen, end - start);
    }
    // key 값이 있는 경우 start 빼고 map 에서도 제거
    else if (map[key]) {
      map[str[start]]--;
      start++;
    } else {
      break;
    }
  }

  return maxLen;
}

솔루션의 풀이는 아래와 같다. 내 풀이와 다른 점은 seen 이라는 객체에 해당 문자열이 등장한 인덱스 값을 저장한다는 것이다. seen 객체를 통해 이전에 등장했던 문자열인지 확인하고, 등장했던 문자열이라면 중복이기 때문에 중복이 없는 문자열의 최대 길이를 구하기 위해 start 값을 seen[char]의 값과 비교해서 옮긴다.

function findLongestSubstring(str) {
  let longest = 0;
  let seen = {};
  let start = 0;

  for (let i = 0; i < str.length; i++) {
    let char = str[i];
    // seen 객체에 현재 char 가 존재한다면 중복이 발생
    if (seen[char]) {
      start = Math.max(start, seen[char]);
    }
    // 현재 위치 - start가 문자열의 길이
    longest = Math.max(longest, i - start + 1);
    seen[char] = i + 1;
  }
  return longest;
}

이 풀이가 직관적으로 이해가 되지 않아서 간단한 예시를 준비했다.

만약 str이 abcdabd 라고 할 때 중복이 없는 가장 긴 부분 문자열의 길이는 abcd => 4가 된다.

seen 객체를 이용해 이 문자열의 각 인덱스를 저장하고, 길이를 구해보도록 하자.

seen 객체와 start 값의 변화는 아래와 같이 확인할 수 있다. 

seen: { a: 1 } start: 0 current: 1
seen: { a: 1, b: 2 } start: 0 current: 2
seen: { a: 1, b: 2, c: 3 } start: 0 current: 3
seen: { a: 1, b: 2, c: 3, d: 4 } start: 0 current: 4
seen: { a: 5, b: 2, c: 3, d: 4 } start: 1 current: 5
seen: { a: 5, b: 6, c: 3, d: 4 } start: 2 current: 6
seen: { a: 5, b: 6, c: 3, d: 7 } start: 4 current: 7