Longest Substring Without Repeating Characters
문자열 s가 주어집니다. 어떤 문자도 두 번 나타나지 않는 가장 긴 부분 문자열(서로 인접한 문자들의 연속 구간)을 찾아 그 길이를 반환하세요.
대문자와 소문자는 서로 다른 문자로 간주하므로 a와 A는 반복이 아닙니다.
함수
- sstring
- 검색할 문자열
- 반환값integer
- 반복되는 문자가 없는 가장 긴 부분 문자열의 길이
제약 조건
1 ≤ s.length ≤ 5 × 104s에는 영문자(소문자 및 대문자)와 숫자만 들어 있습니다.- 대문자와 소문자는 서로 다른 문자입니다.
예제
- 입력
- s = "coddycode"
- 출력
- 5
- 설명
ycode에는 서로 다른 문자가 다섯 개 들어 있습니다. 앞에d를 추가하면dycode가 되며,d가 두 번 나오고 다른 어떤 연속된 다섯 글자 이상에도 반복되는 문자가 없습니다.
- 입력
- s = "racecar"
- 출력
- 4
- 설명
race와ecar는 모두 서로 다른 네 개의 문자를 포함합니다. 다섯 글자로 이루어진 모든 연속 구간에는 같은 문자가 두 번 포함되어 있습니다.
- 입력
- s = "a1b2a3b"
- 출력
- 5
- 설명
- 숫자도 문자로 취급되므로
1b2a3에는 서로 다른 문자가 다섯 개 있습니다. 길이가 6인 두 문자열 모두 두 번째a또는 두 번째b를 포함합니다.
후속 질문
s가 문자와 숫자 대신 모든 유니코드 문자를 담을 수 있다면 무엇을 바꾸시겠어요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
부분 문자열은 문자열에서 연속된 부분이므로, 같은 문자를 두 번 만나지 않고 포함할 수 있는 가장 긴 구간을 찾으면 됩니다.
왼쪽 끝과 오른쪽 끝이 있는 창을 유지하세요. 오른쪽으로 한 번에 한 문자씩 창을 넓히고, 새 문자가 이미 창 안에 있을 때만 왼쪽 끝을 이동하세요.
각 문자가 마지막으로 나타난 인덱스를 저장합니다. 새 문자가 왼쪽 경계 또는 그 이후에 마지막으로 나타났다면, 왼쪽 경계를 해당 인덱스보다 1 큰 값으로 이동합니다. 왼쪽 경계는 절대 뒤로 이동하지 않으며, 정답은 지금까지 찾은 가장 넓은 구간입니다.
풀이
윈도우를 유지하세요. 반복되는 문자가 없는 구간을 양쪽에서 경계로 둘러쌉니다. 오른쪽 경계는 각 문자를 한 번씩 확인하고 왼쪽 경계는 앞으로만 이동하므로, 한 번의 순회로 각 끝 위치에서 끝나는 반복 없는 가장 긴 구간을 찾을 수 있습니다.
모든 부분 문자열을 확인하세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
모든 시작 위치와 끝 위치를 시도하고, 이미 집합에 있는 문자가 나올 때까지 각 부분 문자열의 문자를 집합에 추가하며 테스트합니다. 모든 후보를 테스트하므로 가장 긴 유효한 부분 문자열을 놓칠 수 없습니다.
부분 문자열은 약 n²/2개이며, n = 5 × 10^4일 때 1.25 × 10^9개이고, 테스트 하나는 최대 n개의 문자를 읽을 수 있습니다. 따라서 O(n³)입니다. 여기서 테스트는 최대 63개의 문자만 확인하고 멈춥니다. 문자열에는 서로 다른 문자가 62개뿐이기 때문입니다. 하지만 그래도 테스트가 10억 개를 넘습니다.
알고리즘
best를 0으로 설정합니다.- 모든 시작 인덱스에 대해, 시작 위치부터 문자열의 끝까지 모든 끝 인덱스를 순회합니다.
- 부분 문자열의 문자를 하나씩 빈 집합에 추가하고, 집합에 이미 있는 문자가 나오면 순회를 중단합니다.
- 반복된 문자가 없고 부분 문자열의 길이가
best보다 크면, 그 길이를 저장합니다. best를 반환합니다.
def lengthOfLongestSubstring(s):
def has_no_repeat(start, end):
seen = set()
for k in range(start, end + 1):
if s[k] in seen:
return False
seen.add(s[k])
return True
best = 0
n = len(s)
for start in range(n):
for end in range(start, n):
if has_no_repeat(start, end):
best = max(best, end - start + 1)
return best
집합을 사용한 슬라이딩 윈도우
핵심 아이디어
abc에 반복되는 문자가 없다면, abcd를 확인하는 데는 질문 하나면 됩니다. d가 a, b, c 중 하나인가요? 윈도우의 문자 집합을 사용하면 한 번에 답을 알 수 있습니다.
right를 한 번에 한 단계씩 이동합니다. 새 문자가 집합에 있으면 이전 문자가 사라질 때까지 왼쪽에서 문자를 제거한 다음, 새 문자를 추가하고 길이를 측정합니다. 꼭 필요한 경우에만 문자를 제거하므로, 각 right 위치에서 윈도우는 해당 위치에서 끝나는 반복 없는 가장 긴 구간이며, 최선의 부분 문자열은 어느 위치에선가 끝납니다. 각 문자는 집합에 한 번 들어가고 최대 한 번 나옵니다. O(n).
알고리즘
- 빈 집합으로 시작하고,
left = 0및best = 0으로 설정합니다. - 모든 인덱스를 따라
right를 이동합니다. s[right]가 집합에 있는 동안s[left]를 제거하고left를 한 칸 앞으로 이동합니다.s[right]를 집합에 추가합니다.right - left + 1이best보다 크면 해당 값을 저장합니다.best를 반환합니다.
def lengthOfLongestSubstring(s):
in_window = set() # the characters between left and right
left = 0
best = 0
for right in range(len(s)):
# Shrink from the left until s[right] is no longer inside.
while s[right] in in_window:
in_window.remove(s[left])
left += 1
in_window.add(s[right])
best = max(best, right - left + 1)
return best
마지막으로 확인된 인덱스로 이동하는 슬라이딩 윈도우
핵심 아이디어
이제 left가 어디로 이동해야 하는지 알고 있습니다. 새 문자가 이전에 나온 위치보다 한 칸 뒤입니다. 각 문자의 마지막 인덱스를 맵이나 문자 코드마다 슬롯이 하나씩 있는 배열에 저장하면 left가 한 번에 그곳으로 이동합니다.
해당 인덱스가 left와 같거나 그 뒤에 있을 때만 이동하세요. 더 오래된 문자는 이미 윈도우 밖에 있으므로, 그 위치로 이동하면 left가 뒤로 움직이게 됩니다. 각 단계의 윈도우는 집합 버전에서 만들어지는 것과 같으며, 이제 문자마다 조회 한 번, 비교 한 번, 쓰기 한 번이 필요합니다.
알고리즘
- 문자에서 마지막 인덱스로의 빈 맵을 만들고,
left = 0및best = 0으로 설정합니다. - 모든 인덱스를 차례로 탐색하며, 해당 위치의 문자
ch를 읽습니다. ch가left와 같거나 그 이후의 위치에서 마지막으로 나타났다면,left를 해당 인덱스에 1을 더한 값으로 설정합니다.right를ch의 마지막 인덱스로 기록합니다.right - left + 1이best보다 크면 그 값을 저장합니다.best를 반환합니다.
def lengthOfLongestSubstring(s):
last_seen = {}
start = 0
best = 0
for i, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= start:
start = last_seen[ch] + 1
last_seen[ch] = i
if i - start + 1 > best:
best = i - start + 1
return best
함정과 경계 사례
left를 뒤로 이동시키기.abba에서 마지막a에 도달했을 때 앞쪽의 인덱스 0에 있는a는 이미 윈도우 밖에 있습니다. 인덱스 1로 이동하면 두 번째b가 다시 윈도우에 포함되어 2가 아닌 3이 됩니다.- 윈도우의 길이를
right - left로 계산하기. 양 끝이 모두 윈도우에 포함되므로 1을 더해야 합니다. - 먼저 문자열을 소문자로 바꾸기. 여기서는
a와A가 서로 다른 문자이므로aA의 길이는 2입니다. - 문자가 반복될 때만 길이를 측정하기.
z처럼 반복되는 문자가 없는 문자열에서는 이 조건이 한 번도 충족되지 않아 답이 0이 됩니다.
자주 묻는 질문3
중복 문자가 없는 가장 긴 부분 문자열의 시간 복잡도는 얼마인가요?
슬라이딩 윈도우는 O(n) 시간에 실행되며, 여기서 n은 문자열의 길이입니다. 오른쪽 끝은 각 문자를 한 번씩 읽고 왼쪽 끝은 앞으로만 이동합니다. 추가 공간은 O(k)이며, 여기서 k는 문자열이 담을 수 있는 서로 다른 문자의 개수로, 여기서는 62입니다.
마지막 인덱스를 저장할 때 해시 맵과 배열 중 무엇을 사용해야 할까요?
둘 다 O(n) 시간이 걸립니다. 여기처럼 고정된 소수의 문자 집합을 사용할 때는 문자 코드로 인덱싱하는 배열이 해싱을 피하고 더 빠릅니다.
부분 문자열과 부분 수열의 차이는 무엇인가요?
부분 문자열은 coddycode에서 ode처럼 서로 인접한 문자들의 묶음입니다. 부분 수열은 cdy처럼 문자를 건너뛸 수 있습니다. 이 문제는 부분 문자열을 요구하므로 양쪽 끝이 있는 윈도우가 적합합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def lengthOfLongestSubstring(s):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
s = "coddycode"
예상 출력
5