Minimum Window Substring

Q: Minimum Window Substring의 시간 복잡도는 얼마인가요?

누락 카운터를 사용하는 슬라이딩 윈도우는 O(n + m) 시간에 실행되며, 여기서 n 과 m 은 s 와 t 의 길이입니다. 테이블을 만들 때 t 를 한 번 읽고, s 의 각 문자는 이동당 고정된 비용으로 윈도우에 최대 한 번 들어오고 나갑니다. 추가 메모리는 문자 코드마다 하나의 개수가 있는 테이블이며, 입력 크기에 따라 늘어나지 않습니다.

Q: 왼쪽 가장자리는 왜 절대 뒤로 움직이지 않을까요?

왼쪽 경계는 그 위치에서 시작하는 윈도우가 t 를 덮은 뒤에만 그 위치를 지나갑니다. 그리고 그 윈도우는 해당 시작 위치에서 t 를 덮는 가장 짧은 윈도우였습니다. 그 위치에서 시작해 더 나중에 끝나는 윈도우는 모두 더 길기 때문에, 되돌아가도 더 나은 답을 찾을 수 없습니다. 그렇기 때문에 두 경계 모두 한 번씩 앞으로 이동하며 작업은 선형 시간으로 유지됩니다.

Q: 누락된 카운터는 무엇을 세나요?

이는 윈도우에 아직 없는, t 가 요구하는 문자 복사본의 수이며, need 에서 양수인 값들의 합입니다. 처음에는 t 의 길이와 같고, 윈도우가 t 를 포함하면 정확히 0이 됩니다. 여분의 복사본은 이 값을 바꾸지 않으므로, 모든 문자를 훑는 대신 비교 한 번으로 확인할 수 있습니다.

Q: Minimum Window Substring은 문자열에서 애너그램을 찾는 것과 어떻게 다른가요?

애너그램은 t 의 글자만 정확히 포함하고 다른 글자는 포함하지 않으므로, 윈도우의 길이는 m 으로 고정되어 한 번에 한 단계씩 이동합니다. 여기서는 윈도우에 추가 문자가 포함될 수 있으므로, 윈도우의 길이도 답의 일부입니다. t 를 모두 포함할 때까지 오른쪽으로 늘어나고, 여전히 모두 포함하는 동안 왼쪽으로 줄어듭니다.

어려움슬라이딩 윈도우 해싱

+10

두 문자열 s와 t가 주어집니다. t의 모든 문자를 포함하는 s의 가장 짧은 부분 문자열, 즉 연속된 문자들의 구간을 찾으세요. 문자의 반복 횟수도 셉니다. t에 어떤 문자가 두 번 있으면 부분 문자열에도 그 문자가 최소 두 번 있어야 합니다. 문자의 순서는 중요하지 않으며, 부분 문자열에는 다른 문자가 포함되어도 됩니다.

가장 짧은 길이의 부분 문자열이 여러 개라면 가장 왼쪽에 있는 것을 반환하세요. s의 어떤 부분 문자열도 t의 모든 문자를 포함하지 않으면 빈 문자열을 반환하세요.

함수

minWindow(s: string, t: string) → string

sstring: 검색할 문자열
tstring: 창에 포함되어야 하는 문자와 반복 횟수
반환값string: s의 모든 t를 포함하는 가장 짧은 부분 문자열 중 가장 왼쪽에 있는 부분 문자열 또는 빈 문자열

제약 조건

1 ≤ s.length ≤ 5 × 10⁴
1 ≤ t.length ≤ 10⁴
s와 t에는 영문자만 들어 있습니다. 대문자와 소문자는 서로 다른 문자입니다.
가장 짧은 부분 문자열이 여러 개라면 가장 왼쪽에 있는 것이 답입니다. 그런 부분 문자열이 없으면 ""입니다.

예제

입력: s = "mappingtheplan"t = "nap"
출력: "plan"
설명: 왼쪽부터 읽을 때, n, a, p를 포함하는 첫 번째 구간은 appin이며, 길이는 다섯 글자입니다. 끝에 있는 plan은 네 글자 안에 세 글자를 모두 포함하며, 세 글자로 이루어진 어떤 구간도 세 글자를 모두 포함하지 않습니다.

입력: s = "banana"t = "aan"
출력: "ana"
설명: t는 a 두 개와 n 하나를 요청합니다. 인덱스 1의 ana가 정확히 이를 포함합니다. 두 번째 ana는 인덱스 3에서 시작하며, 가장 왼쪽에 있는 것이 선택됩니다.

입력: s = "Coddy"t = "cd"
출력: ""
설명: Coddy에서 유일한 C는 대문자이며, 대문자와 소문자는 서로 다른 문자입니다. 소문자 c를 포함하는 부분 문자열이 없으므로 답은 빈 문자열입니다.

제출 시 숨은 테스트 +17개

후속 질문

t가 몇 개의 문자만 사용하고 s가 길다면, s의 대부분은 절대 중요하지 않을 수 있습니다. t의 문자가 있는 위치 사이에서만 윈도우가 이동하도록 만들 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

정답은 각 문자가 윈도우에 몇 개씩 포함되어 있는지에 달려 있으며, 문자의 순서에는 달려 있지 않습니다. 또한 최적의 윈도우는 어디에서든 시작할 수 있습니다. 모든 시작점에 대해 모든 끝점을 시도하면 윈도우가 O(n²)개가 됩니다. 해결의 핵심은 양쪽 끝이 앞으로만 이동하는 윈도우입니다. 오른쪽 끝을 늘려 t를 포함시키고, 여전히 포함하고 있는 동안 왼쪽 끝을 줄이며, 누락된 문자의 개수를 세는 카운터 하나로 t를 포함하는지 한 번에 확인할 수 있습니다.

각 시작점에서 윈도우를 확장하기

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

부분 문자열이 시작되는 위치를 고정합니다. 그런 다음 한 번에 문자 하나씩 늘려 가면서 내부의 각 문자가 몇 번 나오는지 세고, 매 단계마다 t를 충족하는지 확인합니다. t에 사용된 서로 다른 문자 u개 각각에 대해, 윈도우에는 t에 있는 것만큼의 문자가 들어 있어야 합니다. 조건을 처음 만족하는 끝 위치가 이 시작 위치에서의 최단 윈도우입니다. 같은 시작 위치에서 더 짧은 윈도우는 모두 먼저 확인했고 조건을 만족하지 못했기 때문입니다. 그 지점에서 멈춥니다.

모든 시작 위치에 대해 이 작업을 수행하고 최단 윈도우를 유지합니다. 시작 위치는 왼쪽부터 차례로 확인하고, 윈도우가 현재 최선보다 엄격히 짧을 때만 최선의 윈도우를 교체하므로, 길이가 같은 윈도우 중에서는 가장 왼쪽에 있는 윈도우가 유지됩니다.

윈도우가 길거나 찾을 수 없으면 느립니다. s에 있는 유일한 Z가 맨 끝에 있고 t가 하나를 요구한다면, 모든 시작 위치에서 끝까지 읽게 됩니다. 약 n²/2단계이며, n = 5 × 10^4일 때 1.25 × 10^9단계입니다. 각 단계에서는 최대 52개의 문자를 확인합니다. 윈도우가 아예 존재하지 않을 때도 마찬가지입니다.

알고리즘

t가 각 문자를 몇 개씩 요구하는지 세고, 사용하는 문자를 나열합니다.
각 start마다 개수 표를 초기화하고, end를 start부터 s의 끝까지 이동하면서 s[end]를 표에 추가합니다.
각 문자를 추가한 후 t의 모든 문자를 확인합니다. 현재 구간에 각 문자가 충분히 있으면 길이를 지금까지의 최선과 비교하고, 엄격히 더 짧으면 이를 최선으로 저장한 뒤 확장을 멈춥니다.
모든 시작 위치를 확인한 후, 최선의 구간을 반환하거나 t의 모든 문자를 포함하는 구간이 없으면 ""를 반환합니다.

def minWindow(s, t):
    need = [0] * 128  # copies of each character code that t asks for
    for ch in t:
        need[ord(ch)] += 1
    letters = [c for c in range(128) if need[c] > 0]
    best_start, best_len = 0, len(s) + 1
    for start in range(len(s)):
        have = [0] * 128  # counts inside s[start..end]
        for end in range(start, len(s)):
            have[ord(s[end])] += 1
            if all(have[c] >= need[c] for c in letters):
                # The first end that covers t gives the shortest window from this start.
                if end - start + 1 < best_len:
                    best_start, best_len = start, end - start + 1
                break
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

모든 문자를 확인하는 슬라이딩 윈도우

핵심 아이디어

두 가지 사실 덕분에 처음부터 다시 시작할 필요가 없습니다. t를 포함하는 윈도우에 문자를 추가해도 계속 포함하고, 무언가를 포함하지 않는 윈도우에서 문자를 제거해도 계속 포함하지 않습니다. 따라서 시작점이 오른쪽으로 이동할 때, t를 포함하는 가장 짧은 윈도우의 끝점은 그대로 있거나 오른쪽으로만 이동할 수 있습니다. 양쪽 끝점은 함께 앞으로 훑어갈 수 있으며, 어느 쪽도 뒤로 돌아가지 않습니다.

right를 s를 따라 이동시키며 각 문자를 개수 테이블에 추가합니다. 윈도우가 t를 포함할 때마다 후보가 됩니다. 현재 최선의 윈도우보다 짧다면 기록한 다음, s[left]를 제거하고 left를 앞으로 이동한 뒤 다시 확인합니다. 윈도우가 t를 더 이상 포함하지 않을 때까지 반복한 다음, 다시 오른쪽으로 확장합니다.

어떤 윈도우도 놓치지 않습니다. L부터 R까지의 최선의 윈도우를 생각해 봅시다. right가 R에 도달하기 전에 left가 L을 지나쳤다면, L에서 시작해 R보다 앞에서 끝나는 윈도우 중 t를 포함하는 것이 있었을 것이고, 그 윈도우는 최선의 윈도우보다 짧았을 것입니다. 따라서 right가 R에 도달하면 축소 루프가 left를 L까지 이동시키고 최선의 윈도우를 기록합니다. 각 끝점은 최대 n번 이동하지만, 확인할 때마다 마지막 확인 이후 개수가 하나만 바뀌었는데도 t에 사용되는 각 문자에 대해 최대 u개의 개수를 읽습니다.

알고리즘

t가 요구하는 각 문자의 개수를 세고 문자를 나열합니다. 빈 윈도우, left = 0, 최적 길이 n+1로 시작합니다.
모든 인덱스를 따라 right를 이동하고 s[right]를 윈도우의 개수에 더합니다.
윈도우에 t의 모든 문자가 충분히 들어 있는 동안, 윈도우 길이가 최적 길이보다 엄격히 짧으면 해당 윈도우를 기록하고, 개수에서 s[left]를 제거한 다음 left를 앞으로 이동합니다.
최적 윈도우를 반환하거나, 최적 길이가 여전히 n+1이면 ""를 반환합니다.

def minWindow(s, t):
    need = [0] * 128  # copies of each character code that t asks for
    for ch in t:
        need[ord(ch)] += 1
    letters = [c for c in range(128) if need[c] > 0]
    have = [0] * 128  # counts inside s[left..right]

    def covers():
        for c in letters:
            if have[c] < need[c]:
                return False
        return True

    left = 0
    best_start, best_len = 0, len(s) + 1
    for right in range(len(s)):
        have[ord(s[right])] += 1  # expand on the right
        while covers():  # shrink from the left while the window still covers t
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            have[ord(s[left])] -= 1
            left += 1
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

누락 카운터를 사용한 슬라이딩 윈도우

핵심 아이디어

같은 윈도우를 유지하고 검사 조건을 숫자 하나로 바꾸세요. need[c]를 t가 요구하는 c의 개수에서 윈도우 안의 개수를 뺀 값이라고 합시다. 양수면 윈도우에 아직 부족한 문자가 있다는 뜻이고, 음수면 남는 문자가 있다는 뜻입니다. missing은 윈도우에 부족한 문자의 총개수이며, 처음에는 t의 길이로 시작합니다. missing이 0일 때 윈도우는 t를 정확히 포함합니다.

이를 갱신하는 데는 한 단계가 듭니다. s[right]가 들어올 때 해당 문자의 need가 0보다 크면 빈자리를 채우므로 missing이 1 줄어듭니다. 어느 경우든 need는 1 줄어들며, 남는 문자라면 0 아래로 내려갈 수 있습니다. s[left]가 나갈 때는 need가 1 증가하고, 이제 0보다 크다면 윈도우에서 t에 필요한 문자가 하나 빠져나간 것이므로 missing이 1 증가합니다. 남는 문자가 들어오고 나가도 missing에는 영향을 주지 않습니다.

s = banana, t = aan을 추적해 보겠습니다. 처음에 need는 a가 2개, n이 1개이고 missing은 3입니다. b는 필요하지 않습니다. 첫 번째 a가 들어오면 missing은 2가 되고, n이 들어오면 1이 되며, 두 번째 a가 들어오면 0이 되므로 bana는 t를 포함합니다. 윈도우를 줄이면 남는 문자 b가 빠져나가고 ana가 남습니다. 길이가 3인 이 부분 문자열이 새로운 최선입니다. 그 a를 빼면 missing이 다시 1이 됩니다. 마지막 a가 들어오면 nana가 다시 조건을 만족하고, 이를 줄이면 두 번째 ana가 됩니다. 길이가 더 짧지는 않으므로 가장 왼쪽의 ana가 유지됩니다.

s의 각 문자는 윈도우에 한 번 들어오고 최대 한 번 나가며, 각 이동에는 고정된 양의 작업이 듭니다. need를 만들 때 t를 한 번 읽습니다. 전체 실행 시간은 O(n + m)이며, 추가 메모리는 128개의 개수를 저장하는 테이블뿐입니다.

알고리즘

need에 t의 각 문자가 나타나는 횟수를 채우고, missing을 t의 길이로, left = 0으로 설정하고 최적 길이를 n+1로 설정합니다.
각 right에 대해 다음을 수행합니다. need[s[right]]가 0보다 크면 missing을 줄인 다음 need[s[right]]를 줄입니다.
missing이 0인 동안, 현재 윈도우의 길이가 최적 길이보다 엄격히 짧으면 해당 윈도우를 기록합니다. 그런 다음 need[s[left]]를 늘리고, 그 값이 이제 0보다 크면 missing을 늘립니다. left를 앞으로 이동합니다.
최적 윈도우를 반환하거나, 최적 길이가 여전히 n+1이면 ""을 반환합니다.

def minWindow(s, t):
    # need[c]: copies of c that t asks for minus copies inside the window.
    # Positive means the window still lacks c; negative means it holds spares.
    need = [0] * 128
    for ch in t:
        need[ord(ch)] += 1
    missing = len(t)  # characters of t the window does not cover yet
    left = 0
    best_start, best_len = 0, len(s) + 1
    for right in range(len(s)):
        c = ord(s[right])
        if need[c] > 0:  # this copy fills a gap
            missing -= 1
        need[c] -= 1
        while missing == 0:  # the window covers t: record it, then shrink
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            c = ord(s[left])
            need[c] += 1
            if need[c] > 0:  # gave away a copy t needs
                missing += 1
            left += 1
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

함정과 경계 사례

대부분의 오답은 잘못된 것을 세거나 잘못된 시점에 윈도우를 기록합니다.

문자 수를 세고 복제본 수를 세지 않음. t = aan에는 a가 두 개 필요하므로, ban은 이를 충족하지 못합니다.
문자가 들어올 때마다 missing을 감소시킴. 세 번째 a는 여분입니다. 이것 때문에 missing을 감소시키면 윈도우에 여전히 n이 없는 상태에서 카운터가 0이 됩니다. need가 0보다 클 때만 감소시키세요.
문자가 나갈 때마다 missing을 증가시킴. 여분 문자를 빼도 윈도우는 계속 t를 충족합니다. need가 0보다 커질 때만 증가시키세요.
축소 루프가 끝난 뒤 윈도우를 기록함. 그때는 더 이상 t를 충족하지 않습니다. 루프 안에서 s[left]를 제거하기 전에 기록하세요.
새 윈도우의 길이가 같을 때 최선의 윈도우를 교체함. 그러면 가장 짧은 윈도우 중 가장 오른쪽에 있는 것이 반환됩니다. 엄격한 less than 비교를 사용하세요.
n을 "찾지 못함"을 나타내는 길이로 사용함. 답이 s 전체일 때도 길이는 n입니다. 두 경우를 구분할 수 있도록 n+1에서 시작하세요.
c - 'a'를 인덱스로 사용하는 26칸짜리 테이블. 대문자는 테이블 범위를 벗어납니다. 문자 코드마다 슬롯을 하나씩 사용하세요.

자주 묻는 질문4

Minimum Window Substring의 시간 복잡도는 얼마인가요?

누락 카운터를 사용하는 슬라이딩 윈도우는 O(n + m) 시간에 실행되며, 여기서 n과 m은 s와 t의 길이입니다. 테이블을 만들 때 t를 한 번 읽고, s의 각 문자는 이동당 고정된 비용으로 윈도우에 최대 한 번 들어오고 나갑니다. 추가 메모리는 문자 코드마다 하나의 개수가 있는 테이블이며, 입력 크기에 따라 늘어나지 않습니다.

왼쪽 가장자리는 왜 절대 뒤로 움직이지 않을까요?

왼쪽 경계는 그 위치에서 시작하는 윈도우가 t를 덮은 뒤에만 그 위치를 지나갑니다. 그리고 그 윈도우는 해당 시작 위치에서 t를 덮는 가장 짧은 윈도우였습니다. 그 위치에서 시작해 더 나중에 끝나는 윈도우는 모두 더 길기 때문에, 되돌아가도 더 나은 답을 찾을 수 없습니다. 그렇기 때문에 두 경계 모두 한 번씩 앞으로 이동하며 작업은 선형 시간으로 유지됩니다.

누락된 카운터는 무엇을 세나요?

이는 윈도우에 아직 없는, t가 요구하는 문자 복사본의 수이며, need에서 양수인 값들의 합입니다. 처음에는 t의 길이와 같고, 윈도우가 t를 포함하면 정확히 0이 됩니다. 여분의 복사본은 이 값을 바꾸지 않으므로, 모든 문자를 훑는 대신 비교 한 번으로 확인할 수 있습니다.

Minimum Window Substring은 문자열에서 애너그램을 찾는 것과 어떻게 다른가요?

애너그램은 t의 글자만 정확히 포함하고 다른 글자는 포함하지 않으므로, 윈도우의 길이는 m으로 고정되어 한 번에 한 단계씩 이동합니다. 여기서는 윈도우에 추가 문자가 포함될 수 있으므로, 윈도우의 길이도 답의 일부입니다. t를 모두 포함할 때까지 오른쪽으로 늘어나고, 여전히 모두 포함하는 동안 왼쪽으로 줄어듭니다.

Python

def minWindow(s, t):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

s = "mappingtheplan"
t = "nap"

기대값

"plan"

Minimum Window Substring

함수

제약 조건

예제

힌트

풀이

각 시작점에서 윈도우를 확장하기

모든 문자를 확인하는 슬라이딩 윈도우

누락 카운터를 사용한 슬라이딩 윈도우

함정과 경계 사례

자주 묻는 질문4

비슷한 문제