[자료구조와 알고리즘] 3. Longest Substring Without Repeating Characters (Feat. Sliding Window, Hash Table)

문제 설명

leetcode Top Interview 150 - 3. Longest Substring Without Repeating Characters
주어진 문자열 s에서 반복되는 문자가 하나도 없이 연속되는 문자열로 만들 수 있는
가장 긴 문자열의 길이를 찾는 문제입니다.

풀어보기

문제에 Hash Table, Sliding Window 태그를 봤지만.. 도저히 접근 방법이 생각나지 않아 🥲
브루트 포스 방법으로 풀었습니다.
이중 반복문을 쓰고 있기 때문에 효율성이 좋지 못합니다..

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let answer = 0;
    let subString = '';
  	// subString의 시작 인덱스 i
    for (let i=0; i<s.length; i++) {
      	// subString에 추가할 문자 인덱스를 찾기 위한 변수 j (i부터 시작)
        for (let j=i; j<s.length; j++) {
          	// subString에 없는 문자일때만 subString에 추가
            if (subString.indexOf(s[j]) == -1) {
                subString += s[j];
            // 한번이라도 반복된 문자가 나오면 반복문 탈출
            } else {
                break;
            }
        }
      	// 가장 긴 길이만 남기기
        if (subString.length > answer) answer = subString.length;
        subString = '';
    }
    return answer;
};

더 좋은 코드

슬라이딩 윈도우 알고리즘 풀이

투 포인터를 이용해서 슬라이딩 윈도우 알고리즘을 사용한 예시입니다.
부분 문자열의 시작(left)과 끝(right) 인덱스를 저장하면서 끝 인덱스를 기준으로 중복 검사를 하는 방법입니다.
left와 right 인덱스로 만들어지는 부분 문자열이 윈도우로 사용되고 가변 길이입니다.

슬라이딩 윈도우 알고리즘은 배열의 일부분을 떼어서 계산하고 이동하면서 전체 배열을 확인하는 알고리즘으로, 배열의 최대 부분 합 문제, 문자열의 중복 없는 가장 긴 부분 문자열을 찾는 문제에 유리합니다.
투 포인터 알고리즘과 비교해서 슬라이딩 윈도우 알고리즘은 무조건 고정 길이라고 생각할 수 있는데, 고정 길이와 가변 길이의 두 가지 타입의 슬라이딩 윈도우가 있습니다.
참고: Linkedin Article - Sliding Window Algorithm by Muhammad Ahsan

var lengthOfLongestSubstring = function(s) {
  if (!s.length) return 0;
  
  let left = 0, right = 0;
  let maxLength = -Infinity;
  const set = new Set();

  // 오른쪽 인덱스가 전체 문자열의 길이를 넘지 않을 때까지 반복합니다.
  while (right < s.length) {
    // 현재 오른쪽 인덱스 문자가 set 변수에 없다면 추가
    if (!set.has(s[right])) {
      set.add(s[right]);
      // 오른쪽 인덱스 증가 -> 슬라이딩 윈도우 길이 증가
      right++;
      // 최대 길이 확인 후 현재 set 변수의 길이가 더 길다면 수정
      maxLength = Math.max(maxLength, set.size);
    } else {
      // 현재 오른쪽 인덱스 문자가 set 변수에 있다면
      // set 변수에서 왼쪽 인덱스 문자 제거 -> 슬라이딩 윈도우 길이 감소
      set.delete(s[left]);
      // 왼쪽 인덱스 증가
      // 오른쪽 인덱스는 변경 사항이 없으므로 방금 중복 검사한 오른쪽 인덱스 문자를 다시 검사하게 됩니다.
      left++;
    }
  }

  return maxLength;
}

예시로 'abbc'를 생각해보면 먼저 left, right가 0인 상태에서 시작하고 첫 슬라이딩 윈도우는 'a'로 시작합니다.

슬라이딩 윈도우 문자열: 'a' -> 'ab' -> (right의 문자 'b'가 중복 검사에서 걸렸기 때문에 left의 문자 'a'가 삭제됩니다.)
-> 'b' -> 'bc' -> (right의 문자 'c'는 전체 문자열의 마지막 인덱스기 때문에 종료됩니다.)

해시 테이블 알고리즘 풀이

해시 테이블 알고리즘을 이용하면 시간, 공간 복잡도가 모두 O(N)입니다.

var lengthOfLongestSubstring = function(s) {
    // keeps track of the most recent index of each letter.
    const seen = new Map();
    // keeps track of the starting index of the current substring.
    let start = 0;
    // keeps track of the maximum substring length.
    let maxLen = 0;
    
    for(let i = 0; i < s.length; i++) {
        // if the current char was seen, move the start to (1 + the last index of this char)
        // max prevents moving backward, 'start' can only move forward
        if(seen.has(s[i])) start = Math.max(seen.get(s[i]) + 1, start)
        seen.set(s[i], i);
        // maximum of the current substring length and maxLen
        maxLen = Math.max(i - start + 1, maxLen);
    } 
    
    return maxLen;  
};

예시로 'abba'를 생각해보면 먼저 start, maxLen은 모두 0으로 시작하고 seen에는 { 'a' => 0 } 이 들어가고 maxLen은 1이 됩니다.
다음 반복문으로 i가 1이 되면 seen은 { 'a' => 0, 'b' => 1 } 이 되고 maxLen은 2가 됩니다.

이제 i가 2일때 이제 'b'가 중복되기 때문에 start는 Math.max()메서드를 사용해서 2와 0중에 더 큰 숫자로 변경됩니다. 만약 중복되는 문자열이 앞부분에 있는 경우에는 seen.get(s[i])+1값이 현재 start 값보다 작을 수도 있고, 그 경우에는 start 인덱스가 배열의 앞부분으로 돌아가버릴 수 있습니다. 그래서 이 둘을 비교하여 더 큰 숫자로만 start 변수에 남깁니다.
그러면 seen은 { 'a' => 0, 'b' => 2 } 이 되고 start는 2가 됩니다.

마지막으로 i가 3이 되면서 seen은 { 'a' => 3, 'b' => 2 } 이 됩니다.
만약 start에 Math.max()메서드를 사용하지 않았다면, 배열의 앞부분에 있는 'a'가 중복되기 때문에 start는 seen.get(s[i])+1값인 1과 현재 start 값인 2를 비교하지 않고 1로 저장되어서, 배열의 더 앞부분에 있는 중복 문자의 인덱스가 start로 계산되어 maxLen이 3이 되버리는 결과가 잘못 나올 수 있습니다.

해시 테이블 알고리즘을 적용할 때는 배열의 인덱스를 잘 생각해서 적용해야겠습니다! 😇