3. Longest Substring Without Repeating Characters

난이도: 중간 (Medium)

링크: LeetCode 3

풀이 날짜: 2025/10/19

 

1. 문제 이해

문자열 s에서 중복 문자가 없는 가장 긴 부분 문자열(substring)의 길이를 구하는 문제이다.

즉, 문자열을 순회하면서 반복되는 문자가 생기기 전까지의 최대 길이를 구해야 한다.

 

2. 접근 방식 — Sliding Window (슬라이딩 윈도우)

슬라이딩 윈도우(Sliding Window)를 사용하면, 중복 문자가 나올 때마다 윈도우를 한 칸씩 이동시키며 O(n) 시간 내에 해결할 수 있다. 현재 “중복이 없는 문자열 구간”을 윈도우로 유지하면서, 새로운 문자를 오른쪽에 추가할 때 중복이 생기면 왼쪽 첫번째를 중복이 없을 때까지 제거한다. 이 과정을 반복하며 매 순간 가장 긴 윈도우의 길이를 갱신하면 된다.

 

 

3. 풀이 코드

풀이 1 — 나의 풀이 (Array + includes + shift 방식)

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {  
  let maxLength = 0;  
  let words = [];
  
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    let hasChar = words.includes(char);
    
    while (hasChar) {      
      words.shift();
      hasChar = words.includes(char);
    }
    words.push(char);
    maxLength = Math.max(words.length, maxLength);
  }

  return maxLength;
};

 

단계	문자	현재 words	중복 발견	조치	maxLength
1	a	[a]	❌	추가	1
2	b	[a, b]	❌	추가	2
3	c	[a, b, c]	❌	추가	3
4	a	[a, b, c]	✅	shift → [b, c] → 추가 → [b, c, a]	3
5	b	[b, c, a]	✅	shift → [c, a] → 추가 → [c, a, b]	3

결국 "abc"의 길이 3이 최대값이 된다.

 

직관적인 이해

• words는 현재 중복 없는 문자 리스트이다.
• 중복이 생기면 shift()로 앞에서부터 제거하여 윈도우를 줄인다.
• 매 순간 words.length가 “현재 유효한 substring의 길이”이다.

복잡도

• 시간 복잡도: O(n²) (includes()와 shift()가 각각 O(n)). 문자열 전체를 이중 반복문으로 탐색하면 O(n²)이 되어 비효율적이다.
• 공간 복잡도: O(k) (현재 substring 길이에 비례)

풀이 2 — Set + 포인터 방식 (최적화된 방법)

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

  for (let right = 0; right < s.length; right++) {
    while (substring.has(s[right])) {
      substring.delete(s[left]);
      left++;
    }
    substring.add(s[right]);
    maxLength = Math.max(maxLength, substring.size);
  }

  return maxLength;
};

핵심 아이디어

• right: 윈도우의 끝을 확장
• left: 중복이 발생하면 왼쪽 포인터를 한 칸씩 이동
• Set: 중복 체크를 O(1)에 처리

복잡도

• 시간 복잡도: O(n)
• 공간 복잡도: O(k)

두 풀이 비교

항목	나의 풀이(Array 방식)	Set + 포인터 방식
접근 방식	배열 + includes + shift	Set + Sliding Window
중복 탐색	O(n) (includes)	O(1) (Set)
시간 복잡도	O(n²)	O(n)
공간 복잡도	O(k)	O(k)
특징	직관적, 이해하기 쉬움	효율적, 최적해에 가까움

 

4. 핵심 정리

개념	설명
문제 유형	문자열, 슬라이딩 윈도우
핵심 변수	left, right, substring(Set)
핵심 아이디어	중복 발생 시 윈도우 시작(left)을 이동시키며 유효 구간 유지
복잡도	시간 O(n), 공간 O(k)
포인트	“중복을 만나면 왼쪽을 줄이고, 아닐 때 오른쪽을 확장한다.”

 

이 문제는 나의 풀이처럼 배열로 접근해도 되지만, 성능 최적화를 위해서는 Set 기반의 투 포인터 방식으로 전환하는 것이 좋다.