[LeetCode] 3. Longest Substring Without Repeating Characters

문제

LeetCode 3. Longest Substring Without Repeating Characters

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

Longest Substring Without Repeating Characters - LeetCode

언어

자바스크립트(JavaScript)

 

접근 방법

1. Loop와 set을 이용하여 푼다.
2. set에 s[i]가 존재한다면, 존재하지 않을 때까지 먼저 나온 문자부터 하나씩 삭제한다. 문자를 하나씩 삭제할 때마다 leftPointer를 1씩 증가시켜 어디서부터 문자열을 만들고 있는지 저장한다.
3. 가장 큰 set의 크기를 저장한다.

코드

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let result = 0;
    let set = new Set();
    let leftPointer = 0;
    for (let i=0; i<s.length; i++){
        // set에 s[i]가 존재한다면, 존재하지 않을 때까지 먼저 나온 문자부터 하나씩 삭제
        while(set.has(s[i])){
            set.delete(s[leftPointer]);
            leftPointer++;
        }
        set.add(s[i]);
        if (set.size > result){
            result = set.size;
        }
    }
    return result;
};

결과

Runtime: 100 ms, faster than 93.63% of JavaScript online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 43.5 MB, less than 71.27% of JavaScript online submissions for Longest Substring Without Repeating Characters.

 

복기

1. O(n2) 복잡도로 두개의 loop를 만들어 문제를 풀면 쉽지만, 성능이 낮다.
2. O(n)으로 풀어야하는데, 슬라이딩 윈도우 알고리즘을 알아야만 풀 수 있다. 몰라서 풀 수 없었다.

참고자료

https://www.youtube.com/watch?v=wiGpQwVHdE0