릿코드 3번 문제 Longest Substring Without Repeating Characters 자바스크립트 문제 해석 및 풀이 Leetcode 3 Javascript

오늘은 릿코드 3번 문제 Longest Substring Without Repeating Characters 자바스크립트 문제입니다.

릿코드 3번 Longest Substring Without Repeating Characters 문제

3번으로 나오는 만큼 인기가 많은 문제입니다.

 

문제설명

이 문제의 경우, 스트링을 입력값으로 받아 모든 substring 중 반복되는 문자를 갖고 있지 않은 substring 길이의 최댓값을 구하는 문제입니다.

예시를 한번 살펴보겠습니다.

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

이렇게 들어왔을 때, 만들어질 수 있는 substring 은 굉장히 많겠죠? 여기서 가장 긴 substring은 길이가 3이 되겠습니다(abc, bca, cab 세 가지 경우 모두 길이가 3이므로 3을 리턴).

이 문제의 경우 Set을 이용한 접근방법을 생각해 볼 수 있습니다.

 

문제풀이

Set 이용

일단 코드부터 살펴보겠습니다.

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const set = new Set();
    let l = 0;
    let max = 0;
    for (let r = 0; r < s.length; r++) {
        while (set.has(s[r])) {
            set.delete(s[l]);
            l++;
        }
        set.add(s[r]);
        max = Math.max(max, r-l+1);
    }
    return max;
};

우선 셋 객체를 만들어주고, left를 뜻하는 l, 최종 리턴값인 max를 0으로 셋 해 줍니다.

루프를 돌며 set객체가 현재 인덱스의 문자를 가지고 있는지 확인하고, 그렇다면 set에서 l인덱스를 지워준 후 l을 하나 더해줍니다. 이렇게 해서 더 이상 현재 인덱스 위치의 set객체가 해당 문자를 가지고 있지 않을 때까지 계속 l번째 인덱스를 지워가며 l포인터를 옆으로 이동해 나갑니다.

그런 다음 항상 set에 현재 인덱스 문자를 추가해 주고, max 값을 업데이트시킵니다.

 

예제 1로 코드에서의 변화를 살펴보겠습니다.

Input: s = "abcabcbb"

변수 r의 값 변화에 따른(시간순서) 테이블 (맨 위 자료는 초기값)

r	set	l	max
	()	0	0
0	('a')	0	1
1	('a', 'b')	0	2
2	('a', 'b', 'c')	0	3
3	('b', 'c', 'a')	1	3
4	('c', 'a', 'b')	2	3
5	('a', 'b', 'c')	3	3
6	('c', 'b')	5	3 (2 < 3)
7	('b')	7	1 (1 < 3)

Set 이용 결과

Set 이용해서 푼 Longest Substring Without Repeating Characters 문제

결과가 나쁘지 않게 나왔습니다.

• 시간복잡도: O(n) 배열의 길이만큼 돌기 때문에 O(n)입니다. for loop내의 while루프의 경우, for loop내의 변수의 변화에 따른 컨디션체크기 때문에 O(n)의 복잡도를 가지지 않습니다. 단순히 포인터만 옆으로 옮기는 것이기 때문입니다.
• 공간복잡도: O(n) substring의 최대길이는 인자로 받은 string만큼이기 때문에(모든 캐릭터가 유니크한 경우) set의 크기는 최악의 경우 O(n)이 됩니다.

---

※ 앞으로 모든 문제를 JavaScript로 올릴 예정입니다. 릿코드 연습을 하며 올린 포스팅이므로 간혹 틀린 부분이 있을 수 있습니다. 혹시 잘못된 부분이 있을 경우 댓글 남겨주시면 감사드리겠습니다. 다른 문제 풀이도 깃헙에서 확인할 수 있습니다.