문제 설명

Longest Substring Without Repeating Characters - LeetCode

주어진 문자열 s에서 중복 문자가 없는 가장 긴 부분 문자열(substring) 의 길이를 반환하는 문제입니다.

✅ 부분 문자열(Substring) 조건:

  • 연속된 문자만 포함해야 함 (순서를 바꾸면 안 됨)
  • 중복 문자가 없어야 함
  • 최대 길이를 반환

해설

1️⃣ 브루트포스 (O(N²)) - 비효율적

  • 모든 가능한 부분 문자열을 생성하여 중복이 없는지 검사 → O(N²)
  • 비효율적이므로 사용하지 않음

2️⃣ 투 포인터 + 해시셋 (슬라이딩 윈도우, O(N)) [추천]

  • 해시셋(Set) 을 사용하여 중복 여부를 빠르게 검사
  • 두 개의 포인터 (left, right) 를 사용하여 윈도우 크기를 조절
  • 시간 복잡도: O(N) (각 문자를 한 번씩만 처리)

코드 풀이

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def lengthOfLongestSubstring(s: str) -> int:
    char_set = set()  # 중복 문자를 빠르게 찾기 위한 해시셋
    left = 0  # 윈도우의 왼쪽 포인터
    max_length = 0  # 최대 길이 저장

    for right in range(len(s)):  # 오른쪽 포인터 이동
        while s[right] in char_set:  # 중복 문자가 있으면 왼쪽 포인터 이동
            char_set.remove(s[left])
            left += 1

        char_set.add(s[right])  # 새로운 문자 추가
        max_length = max(max_length, right - left + 1)  # 최대 길이 갱신

    return max_length

Javascript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

var lengthOfLongestSubstring = function(s) {
    let charSet = new Set();  // 중복 확인을 위한 해시셋
    let left = 0;  // 윈도우의 왼쪽 포인터
    let maxLength = 0;  // 최대 길이 저장

    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;
};

참고 및 출처

programmers Coding Test
LeetCode - The World’s Leading Online Programming Learning Platform