Longest Substring Without Repeating Explanation

Problem Summary

Write a function that finds the length of the longest substring without repeating characters.

Detailed Explanation

이 문제는 **슬라이딩 윈도우(Sliding Window)** 기법을 학습합니다. LeetCode의 유명한 문제입니다. **슬라이딩 윈도우란?** 배열이나 문자열에서 연속된 부분을 "창문"처럼 이동시키며 탐색하는 기법입니다. **알고리즘 전략** - start: 현재 윈도우의 시작 인덱스 - i: 현재 윈도우의 끝 인덱스 - seen: 각 문자의 마지막 등장 위치 **동작 원리** 1. 문자를 순회하며 Map에 위치 저장 2. 중복 문자 발견 시 윈도우 시작점 이동 3. 각 단계에서 최대 길이 갱신 **"abcabcbb" 처리 과정** - i=0, 'a': start=0, max=1 - i=1, 'b': start=0, max=2 - i=2, 'c': start=0, max=3 - i=3, 'a': 중복! start=1, max=3 - i=4, 'b': 중복! start=2, max=3 - i=5, 'c': 중복! start=3, max=3 - ... **seen.get(str[i]) >= start 조건** 이전에 본 문자가 현재 윈도우 안에 있는 경우에만 시작점을 이동합니다. 윈도우 밖의 중복은 무시합니다. **왜 O(n)인가?** 각 문자를 한 번씩만 방문하고, Map 연산은 O(1)입니다.

Solution Code

solution.js

function lengthOfLongest(str) {
  const seen = new Map();
  let max = 0, start = 0;
  for (let i = 0; i < str.length; i++) {
    if (seen.has(str[i]) && seen.get(str[i]) >= start) {
      start = seen.get(str[i]) + 1;
    }
    seen.set(str[i], i);
    max = Math.max(max, i - start + 1);
  }
  return max;
}

Key Concepts from This Problem

1. 슬라이딩 윈도우

2. Map 자료구조

3. 부분 문자열

4. 최적화 알고리즘

Common Mistakes

✗ 중복 문자가 현재 윈도우 밖에 있는 경우를 처리해야 합니다

✗ 길이 계산은 i - start + 1입니다 (+1 잊지 마세요)

✗ 빈 문자열의 경우 0을 반환해야 합니다

Hints

Hint 1: 슬라이딩 윈도우를 사용하세요.

Hint 2: Map으로 문자 위치를 기록하세요.

Complexity Analysis

Time Complexity

O(n)

Grows linearly with input size

Space Complexity

O(min(n, m))

Related Tags

#알고리즘 #슬라이딩윈도우 #Map