← 전체 회차
A-016● Day 162026.05.18mediumleetcode #3neetcode150

중복 없는 최장 부분 문자열

#hash-table#string#sliding-window
↗ leetcode #3 · longest-substring-without-repeating-characters
01

문제

· problem
P.016

중복 없는 최장 부분 문자열

↗ leetcode #3

문자열 s가 주어질 때, 중복된 문자가 없는 최장 부분 문자열의 길이를 구하세요.

제약
  • · 0 ≤ s.length ≤ 5 × 10⁴
  • · s consists of English letters, digits, symbols and spaces
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
"abcabcbb"
3
example 2input → output
"bbbbb"
1
example 3input → output
"pwwkew"
3
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    부분 문자열은 반드시 연속되어야 하나요?
  • ☐
    빈 문자열을 입력받으면 어떤 값을 반환해야 하나요?
  • ☐
    같은 길이의 유효한 부분 문자열이 여러 개 있으면 어떻게 하나요?
  • ☐
    문자의 종류가 최대 26개(영문)라는 것이 왜 중요한가요?
  • ☐
    'bca'는 'abcabcbb'의 유효한 부분 문자열이 될 수 있나요?
  • ☐
    결과로 부분 문자열 자체를 반환해야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 문자 집합 초기화
○
charSet = set()
○
charSet = {}
○
charSet = []
step 2· 왼쪽 포인터 초기화
○
l = 0
○
l = 1
○
l = -1
step 3· 결과 변수 초기화
○
res = 0
○
res = 1
○
res = len(s)
step 4· 오른쪽 포인터 반복
○
for r in range(len(s)):
○
for r in range(1, len(s)):
○
for r in s:
step 5· 중복 감지 조건│ 중첩
○
while s[r] in charSet:
○
if s[r] in charSet:
○
while s[l] in charSet:
step 6· 현재 문자 추가│ 중첩
○
charSet.add(s[r])
○
charSet.add(s[l])
○
charSet.update([s[r]])
step 7· 최대 길이 업데이트│ 중첩
○
res = max(res, r - l + 1)
○
res = max(res, r - l)
○
res = r - l + 1
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def lengthOfLongestSubstring(self, s: str) -> int:
3
        charSet = set()
4
        l = 0
5
        res = 0
6
7
        for r in range(len(s)):
8
            while s[r] in charSet:
9
                charSet.remove(s[l])
10
                l += 1
11
            charSet.add(s[r])
12
            res = max(res, r - l + 1)
13
        return res
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
"abcabcbb"
→
3
case 2
"bbbbb"
→
1
case 3
"pwwkew"
→
3
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.