[Leetcode] 3. Longest Substring Without Repeating Characters - JS

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-interview-150

 

 

1. 문제 분석

문제분석
--------------------
- 문자열 s가 주어진다.
- 고유한 문자로만 이루어진 가장 긴 부분 문자열의 길이를 반환하라

제한조건
--------------------
- 0 <= s.length <= 5 * 10^4
- s는 영어, 숫자, 기호, 공백으로 구성된다.

 

2. 접근 방법

접근방법 - Sliding Window
--------------------
1. maxLen = 0, subStr = '', start = 0, end = 0으로 초기화
2. start <= end && end < s.length 만족하면 반복한다.
3. subStr에 end에 위치한 문자 포함했는지(includes) 확인
    - 만약 포함하지 않았다면, subStr에 추가하고 end 우측 이동
    - 만약 포함한다면, maxLen 업데이트하고 중첩 반복문 실행
        - start 이동 후 s.slice(start, end)에 end에 위치한 문자가 포함되었는지 확인
            - 만약 있다면 start 이동
            - 만약 없다면 반복 종료
4. 반복문 종료되면 maxLen을 반환

 

 

3. 코드

var lengthOfLongestSubstring = function(s) {
    let maxLen = 0;
    let subStr = '';
    let start = 0;
    let end = 0;

    while (start <= end && end < s.length) {
        let letter = s[end];
        if (!subStr.includes(letter)) {
            subStr += letter;
            end++;
        } else {
            let slicedSubStr = s.slice(start, end)
            while (slicedSubStr.includes(letter)) {
                slicedSubStr = s.slice(++start, end)
            }
            subStr = slicedSubStr;
        }
        maxLen = Math.max(maxLen, subStr.length);
    }
    return maxLen;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)

 

start, end 포인터를 가지고 subStr 안에 중복되는 문자가 없으면 end 포인터를 이동시켜 window의 최대 크기를 구할 수 있다.

이 후 subStr 안에 중복되는 문자가 등장할 경우, 중복되는 문자가 등장하지 않을 때 까지 start 포인터를 이동시켜 다음 부분 문자열을 비교해 나간다.

 

sliding window 패턴으로 풀기위해 저번에 풀었던 문제의 접근법을 참고하였다. 비슷한 패턴의 문제를 2번 풀어보니 이제 조금 감이 오는 것 같다.

 

 

5. 다른 사람 풀이 - Sliding Window & Set

다른 사람 풀이를 참고했다. set 자료구조를 사용하여 코드를 더 간결히 할 수 있다.

var lengthOfLongestSubstring = function(s) {
    let left = 0;
    let maxLength = 0;
    let charSet = new Set();

    for (let right = 0; right < s.length; right++) {
        while (charSet.has(s[right])) {
            charSet.delete(s[left]);
            left++;
        }

        charSet.add(s[right]);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;    
};

 

set 자료구조는 배열과 비슷하게 인덱스로 데이터 참조가 가능하지만 중복된 값은 가질 수 없다.

right에 위치한 문자열을 추가하면서 right 포인터를 이동시킨다.

단, 추가하기 전 set에 right에 위치한 문자열이 존재하면 set에서 left에 위치한 문자열을 제거하고 left 포인터를 이동시킨다.

 

길이는 right, left 포인터의 차이 + 1로 구할 수 있다.