[75 LeetCode] 8 - Longest Substring Without Repeating Characters

[75 LeetCode]는 코딩테스트 연습을 위해 한 페이스북 개발자가 추천하는 75가지 알고리즘 문제를 풀어보는 시리즈이다.

블라인드 원문:
https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU

문제 링크: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

Longest Substring Without Repeating Characters - LeetCode

주어진 문자열의 
1. substring 중에
2. 중복되는 문자가 없는
3. 가장 긴
substring을 찾아야한다.

가장 먼저 드는 생각은 문자열을 순회하는 index로 start를 잡고,
start부터 중복이 있을 때까지 순회하며 (2중 반복문)
중복이 나오면 max 길이를 체크 후 start 순회를 계속하는 것이다.

여기서 한 가지 포인트를 찾은 것은 abcded 라는 예를 보면, abcded에서 ded 중복을 발견한 순간, b부터 시작하는 문자열, c부터 시작하는 문자열은 ded로 인해서 앞의 abcded보다 짧을 수 밖에 없다. 즉, e부터 다시 순회를 이어가면 된다.

그러기 위해선 문자들의 인덱스를 저장해둘 필요가 있었다.
이를 바탕으로 첫번째 구현을 했다.

function lengthOfLongestSubstring(s: string): number {
    if(s.length === 0) return 0;
    if(s.length === 1) return 1;
    
    let max = 0;
    let start = 0;

    while (true) {
        let iter = start + 1;

        const cache = { [s[start]]: start };

        while(true) {
            if (iter >= s.length) {
                return Math.max(max, iter - start);
            }

            const char = s[iter];
            if (char in cache) {
                max = Math.max(max, iter - start);
                start = cache[char] + 1;
                break;
            } else {
                cache[char] = iter;
                iter++;
            }
        }
    }
};

이렇게 짠 경우, O(n^2)이므로, 시간 내 통과는 하지만 굉장히 느린 것을 알 수 있다.

개선점을 생각해보니, start_(i)에 대한 순회가 끝난 후에 start_(i+1) ~ iter은 중복 체크가 된 구간이므로, 다음 start 순회에서는 start_(i+1) ~ iter 구간에 대한 체크는 필요가 없다는 것이다.

즉, 중복이 발생 하면
start = 중복이 발생한 곳 + 1
iter = iter + 1 (기존에는 2중 반복으로 start + 1부터 iter가 돌았다.)

function lengthOfLongestSubstring(s: string): number {
  if(s.length === 0) return 0;
  if(s.length === 1) return 1;
  
  let max = 0;
  let start = 0;
  let iter = 1;
  const cache = {};

  while (iter < s.length) {
    cache[s[start]] = start;

    while(iter < s.length) {
      const char = s[iter];
      if (char in cache && cache[char] >= start) {
        max = Math.max(max, iter - start);
        start = cache[char] + 1;
        cache[char] = iter;
        iter++;
        break;
      } else {
        cache[char] = iter;
        iter++;
      }
    }
  }
  return Math.max(max, iter - start);
};

이렇게 작성한 경우 중복은 제거되어 O(n)의 알고리즘이 된다. (iter이 n개의 item을 순회)

하지만, 반복문을 아직 2회 중첩하여 사용하고 있다.

O(n)이므로 반복문을 잘 구성하면 한개로 줄일 수 있다. 이는 풀이를 보고 찾았다.

function lengthOfLongestSubstring(s: string): number { 
    let max = 0;
    const cache = new Map();

    for (let i =0, j=0; j < s.length; j++) {
        if (cache.get(s[j]) >= 0) {
            i = Math.max(i, cache.get(s[j]) + 1);
        }

        max = Math.max(max, j - i + 1)
        cache.set(s[j], j);
    }

    return max;
};

LeetCode에서 editorial으로 설명과 영상풀이를 제공해서 한 번 참고하면 좋을 것 같다.

참고로 위 알고리즘은 Sliding window라고 부른다.

 

추가)

알고보니 3년 전 취준할 때 python으로 풀었던 기록이 있었다. 그 때는 DP를 써보려고 어떻게 노력 했던 것 같다.