리트코드 3번: Longest Substring Without Repeating Characters

문제
Given a string s, find the length of the longest substring without repeating characters.

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

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

 

 

내 풀이

내 생각의 흐름
1. 문자열 s를 0부터 s.length까지 순회하고 s[i]를 temp에 저장해야겠다.
2. s[i...] 순회할 때마다, 현재까지의 temp 길이가 result보다 길면 temp를 result에 저장하자.
3. temp에는 반복되는 문자가 없어야한다. 즉, temp도 0부터 temp.length까지 순회해야겠네?
4. temp[j...]에 s[i]와 같은 문자가 있는 지 순회해보고 없으면 temp에 s[i]를 추가하자.
5. 만약 temp에 s[i]가 있으면? 음.. 일단 반복문은 멈추고 s[i]와 같은 문자가 있던 temp[j] 바로 다음 인덱스부터 문자열을 자른 후, s[i]를 추가하자.

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {

    let result = '';
    let temp = '';

    let i = 0;
    let j = 0;

    for (i = 0; i < s.length; i++) {
        for (j = 0; j < temp.length; j++) {
            if (temp[j] === s[i]) {
                break;
            }
        }


        if (j === temp.length) {
            temp += s[i]
        } else {
            temp = temp.substring(j + 1, temp.length) + s[i]
        }

        if (result.length < temp.length) {
            result = temp;
        }
    }

    return result.length;
};

 

시간 복잡도
바깥쪽 for 루프는 문자열 s 길이만큼 반복하므로 s 길이를 n으로 한다면, O(n)의 시간 복잡도를 가진다.
안쪽 for 루프는 temp의 길이만큼 반복되며 최악의 경우 s의 길이 n만큼 반복할 수 있다. 따라서 O(n)의 시간 복잡도를 가진다.
정리하면, 전체 시간 복잡도는 O(n^2)이 된다.

공간 복잡도
result, temp 는 s 길이에 따라 크기가 변한다.
그러므로 공간 복잡도는 O(n)이 된다.

---

 

고수의 풀이

윈도우 슬라이딩 기법

고수는 윈도우 슬라이딩 기법을 이용하여 O(n)의 시간 복잡도를 가진 알고리즘을 구현했다.
그의 말에 의하면, 윈도우 슬라이딩 기법은 투 포인트를 이용해 중첩 루프의 수를 줄여 시간 복잡도를 줄일 수 있다고 한다.
이 기법은 자료구조가 배열 또는 문자열일 때 쓰면 좋고 오늘 문제처럼 주어진 문자열 또는 배열에서 가장 긴, 가장 짧은 서브 값을 찾으려고 할 때 유용하다.

Set 활용

나의 경우 문자열을 temp에 저장하고 s[i...]와 중복인지를 temp의 길이만큼 순회하는 방식으로 확인했다.
그러나 고수는 Set을 이용해 중복 판단을 O(1)의 시간 복잡도로 해결했다.
자바스크립트의 Set은 내부적으로 해시테이블 형태로 요소들을 저장하기 때문에 요소 존재 여부를 확인하는데 O(1)의 시간복잡도가 걸린다. 물론 최악의 경우 O(n)에 가까워질 수 있지만 드물다.

 

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    const set = new Set();
    let left = 0;
    let right = 0;
    let maxLength = 0;

    while (right < s.length) {
        if (!set.has(s[right])) {
            set.add(s[right])
            maxLength = Math.max(set.size, maxLength);
            right++;
        } else {
            set.delete(s[left]);
            left++;
        }
    }

    return maxLength
};