3. Longest Substring Without Repeating Characters | "Two Pointer, Set(중복방지), 윈도우 유지란?"

[soozynn]

문제

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.

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.

내가 푼 풀이

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let result = 0;
    let startIndex = 0;
    let endIndex = 0;
    const set = new Set();

    if (s.length === 1) return 1;

    while (startIndex < s.length && endIndex < s.length) {
        if (!set.has(s[endIndex])) {
            set.add(s[endIndex]);
            result = set.size > result ? set.size : result;
            endIndex += 1;
        } else {
            set.clear();
            startIndex += 1;
            endIndex = startIndex;
        }
    }

    return result;
};

[soozynn]

🔍 현재 로직의 병목

set.clear();
startIndex += 1;
endIndex = startIndex;

→ 이건 중복이 발생했을 때 전체 Set을 날리고, 다시 새로 시작하는 방식이라서 최악의 경우엔 O(n²)에 가까워짐

---

최적화 풀이

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

    while (end < s.length) {
        if (!set.has(s[end])) {
            set.add(s[end]);
            maxLength = Math.max(maxLength, end - start + 1);
            end++;
        } else {
            // 중복된 문자를 제거하면서 윈도우 유지
            set.delete(s[start]);
            start++;
        }
    }

    return maxLength;
};

→ 실질적으로 테스트 코드를 돌렸을 때 성능차이가 매우 크게 차이남.
→ ⭐️ 중복이 있을 경우, start 문자열을 제거하고 start를 우측으로 옮겨줌으로써 윈도우를 슬라이딩 하며 조절하여 전체 문자열을 한 번만 훑는다

[soozynn]

슬라이딩 윈도우(sliding window)란?

배열이나 문자열 안에서 일정 범위(연속된 구간)를 유지한 채, 그 범위를 앞뒤로 이동시키며 탐색하는 알고리즘 패턴

---

🪟 "윈도우"라는 표현을 쓰는 이유:
💡 1. 프레임(frame)처럼 범위를 본다는 개념
예를 들어 "abcabcbb"에서 start = 0, end = 2면 현재 보고 있는 부분은 "abc"
마치 문자열 위에 **투명한 창(window)**을 얹어서 그 일부를 들여다보는 느낌

💡 2. 구간이 고정된 '창틀'처럼 움직이기 때문
"a|b|c|a|b|c|b|b" 라는 문자열이 있다면
창(window) = [start ... end]는 일정 크기로 유지되거나 줄어들거나 늘어나면서 양 끝만 움직이며 탐색
-> 프로그래밍적 시선에서 창처럼 데이터를 일정 범위만 본다는 뜻

💡 3. 탐색 효율을 높이기 위한 전략이기 때문
브루트포스는 전체 조각을 다 잘라서 다 보지만
슬라이딩 윈도우는 이미 본 범위를 활용해서 겹치는 계산을 줄인다
-> 유리창을 왼쪽에서 오른쪽으로 쭉 옮기며 하나씩 보는 느낌

---

“슬라이딩 윈도우에서 윈도우 유지란 뭘까?”

✅ 윈도우 유지란?
현재 두 포인터(start, end)가 가리키는 범위 = “하나의 윈도우(창)”
슬라이딩 윈도우 기법에서는 이 범위를 유지하면서 문제 조건을 만족시키는 가장 긴/짧은 구간을 찾는 게 핵심

🔍 예시

s = "abcabcbb"
         ↑
     start
            ↑
           end

여기서 start = 0, end = 3이면 현재 윈도우는 "abc"
중복 문자가 s[end]에 생겼다면 → "a"를 제거하고 start를 1칸 오른쪽으로 옮겨 "bca" → "ca" 처럼 윈도우를 유지
즉, 전체 문자열을 다시 탐색하는 게 아니라, “이 창을 유지한 채” start만 밀면서 구간을 조절

🔁 왜 중요하냐면?
윈도우를 유지하지 않고 매번 Set.clear()를 하거나 end = start로 리셋하면 → 항상 처음부터 다시 세는 구조
반면, 중복된 문자만 제거하고 윈도우를 유지하면 → 같은 문자도 두 번 이상 확인하지 않게 되고→ 시간 복잡도 O(n)이 가능

📌 비유:
“윈도우 유지”는 창문을 통째로 버리지 않고, 더러워진 유리 조각 하나만 치우고 계속 보는 것과 같음.

[soozynn]

[ 미디엄 문제를 풀면서 느꼈던 생각과 이번 주차 회고 ]

여러 문제를 접하고 풀어나가면서, 시간은 많이 들지만 내 손에 쥐어지는 무기들이 점점 늘어간다는 느낌을 받고 있다.
패턴을 하나씩 알아가다 보니, 문제를 볼 때마다 익숙한 방식이 보이면 서랍장에서 무기를 꺼내 쓰는 느낌이 든다.

물론 시간이 지나며 어떤 무기들은 흐릿해지기도 하지만, 반복해서 문제를 풀다 보면 결국엔 온전히 내 것이 될 거라고 믿는다.
이번 주부터 시작한 미디엄 문제들은 예상보다 더 많은 시간이 들지만, 꾸준히 해낸다면 예전 이지 문제를 풀 때처럼 점점 속도도 붙을 것이라고 생각한다.