LeetCode Longest Substring Without Repeating Characters (JavaScript)

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

문제 설명

Given a string s, find the length of the longest substring without duplicate characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3. Note that "bca" and "cab" are also correct answers.

Example 2:

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

Example 3:

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.

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

---

문제 풀이

접근 방식

• 포인터를 2개 두어 해당 포인터의 길이 차이를 구하도록 함 (left, right)
• 두 포인터 안에는 중복되는 문자가 존재하지 않아야 함 -> set 을 통해 관리
  • 특정 문자가 없어질 때까지 set 배열에서 제거 (while 문)
• 현재 위치의 문자를 넣고 길이의 최댓값 계산 (right - left + 1)

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

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

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

    return answer;
};

---

결론

O(n)의 시간복잡도로 해결.

중간에 문자열을 자르고 하는 메서드를 사용할 경우 길이가 길어짐에 따라 시간 초과 오류가 발생할 수 있음.

set을 통해 O(1)로 검색을 하도록 했고, for문을 한 번만 탐색해도 최대 길이를 구할 수 있도록 했음

 

* for문 안에 while문이 있으면 O(n^2)이 아닌가? 아니다.

for문 안에 while문으로 O(n^2)처럼 보일 수 있지만 실제 동작을 보면 다른걸 알 수 있다.

• right 포인터 : 문자열을 처음부터 끝까지 한 번만 탐색 (n번)
• left 포인터 : while 문 안에서 동작하지만, 전체 과정을 보면 문자열의 각 인덱스를 최대 한 번씩만 탐색함 (n번)
  • 즉, 한 번 left가 지나간 자리는 다시 돌아가지 않음 -> O(n^2)이 안되는 이유

따라서 모든 문자는 최대 두 번씩만 처리되기 때문에 연산 횟수는 2n에 비례해서 O(n)의 시간복잡도를 가지게 된다.