Minimum Window Substring

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

누락된 카운터 윈도우는 O(n + m) 시간에 실행되며, 여기서 n 과 m 은 s 와 t 의 길이입니다. 테이블을 만들 때 t 를 한 번 읽고, s 의 각 문자는 최대 한 번 윈도우에 들어갔다가 나옵니다. 추가 메모리는 문자 코드당 하나의 카운트입니다.

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

왼쪽 끝은 그 위치에서 시작하는 윈도우가 t 를 포함한 뒤에만 해당 위치를 지나며, 그 윈도우는 그 시작점에서 조건을 만족하는 가장 짧은 윈도우였습니다. 그 위치에서 시작해 더 늦게 끝나는 윈도우는 모두 더 길기 때문에, 되돌아가도 더 나은 답을 찾을 수 없습니다.

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

애너그램은 t 의 문자를 정확히 모두 포함하므로, 해당 윈도우의 길이는 m 으로 고정되며 한 번에 한 단계씩 이동합니다. 여기서는 추가 문자가 허용되므로 길이도 답의 일부입니다. 윈도우는 t 를 포함할 때까지 커지고, 계속 포함하는 동안 줄어듭니다.

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

+10

두 문자열 s와 t가 주어집니다. 반복 횟수까지 고려하여 t의 모든 문자를 포함하는 s의 가장 짧은 부분 문자열을 찾으세요. t에 어떤 문자가 두 번 있으면 부분 문자열에도 그 문자가 최소 두 번 있어야 합니다. 순서는 상관없으며 다른 문자가 포함되어도 됩니다.

가장 짧은 부분 문자열이 여러 개라면 가장 왼쪽에 있는 것을 반환하세요. 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와는 다른 문자입니다. 소문자 c를 포함하는 부분 문자열이 없으므로 답은 빈 문자열입니다.

후속 질문

t의 글자 수가 적고 s가 길면, s의 대부분은 전혀 중요하지 않습니다. t의 글자가 있는 위치 사이에서만 창이 이동하도록 만들 수 있나요?

힌트

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

3개 중 0개 열림

풀이

윈도우에서는 문자의 순서가 아니라 개수만 중요합니다. 윈도우가 t를 포함할 때까지 오른쪽 끝을 이동한 다음, 여전히 포함하는 동안 왼쪽 끝을 이동합니다. 어느 쪽 끝도 뒤로 돌아가지 않습니다. 누락된 문자의 개수를 세면 윈도우가 t를 포함하는지 한 번에 알 수 있습니다.

모든 시작 위치에서 윈도우를 확장합니다

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

핵심 아이디어

시작점을 고정하고 문자를 한 번에 하나씩 추가하며, 각 문자의 개수를 셉니다. 매 단계마다 u개의 문자를 각각 확인합니다. 조건을 만족하는 첫 번째 끝점이 이 시작점에서 가장 짧은 포함 윈도우를 제공하므로, 그 지점에서 멈춥니다. 시작점은 왼쪽에서 오른쪽으로 이동하고, 엄격히 더 짧은 윈도우만 최선의 윈도우를 대체하므로, 길이가 같으면 가장 왼쪽 윈도우가 유지됩니다.

윈도우가 존재하지 않으면 모든 시작점에서 s의 끝까지 읽습니다. 약 n²/2단계이며, n = 5 × 10^4일 때 1.25 × 10^9입니다.

알고리즘

t가 요구하는 각 문자의 개수를 센다.
각 start마다 개수 표를 초기화하고 end를 오른쪽으로 이동하며 s[end]를 더한다.
윈도우에 모든 문자가 충분히 들어 있으면, 현재 최선보다 엄격히 짧을 때 이를 유지하고 다음 시작 위치로 이동한다.
최선의 윈도우를 반환하거나, 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]

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

핵심 아이디어

문자를 포함 윈도우에 추가하면 계속 포함 상태가 유지되고, 무언가를 놓치는 윈도우에서 문자를 제거하면 계속 놓치는 상태가 유지됩니다. 따라서 시작점이 오른쪽으로 이동할수록 최단 포함 윈도우의 끝점은 왼쪽으로 이동하지 않습니다.

놓치는 윈도우는 없습니다. L부터 R까지의 최적 윈도우를 살펴보겠습니다. right가 R에 도달하기 전에 left가 L을 지나려면, L에서 시작하는 더 짧은 윈도우가 t를 포함해야 합니다. 따라서 right가 R에 도달하면, 축소 과정에서 left가 L까지 이동하며 해당 윈도우를 기록합니다.

각 끝점은 최대 n번 이동하지만, 각 검사에서는 최대 u개의 개수를 읽습니다. 따라서 시간 복잡도는 O(n·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를 정확히 포함합니다.

need가 0보다 큰 상태에서 문자가 들어오면 부족한 문자를 채우므로 missing이 감소합니다. 문자를 제거했을 때 need가 0보다 커지면 부족한 문자가 생기므로 missing이 증가합니다. 여분은 missing에 영향을 주지 않습니다. banana에서 t = aan인 경우, missing은 bana에서 처음 0이 되고, 여분인 b를 제거해도 ana는 여전히 조건을 충족합니다.

각 문자는 고정된 비용으로 한 번씩 들어오고 나갑니다. 시간 복잡도는 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도 개수에 포함되어, 윈도우에 n이 없는데도 missing이 0이 될 수 있습니다.
길이가 같은 경우 최선의 윈도우를 교체하는 경우. 두 번째 예제에서는 인덱스 3의 ana를 반환합니다.
n을 "찾을 수 없음"을 나타내는 길이로 사용하는 경우. 답이 s 전체일 때도 길이가 n이므로, n+1에서 시작하세요.
c - 'a'를 인덱스로 사용하는 26개 슬롯의 테이블. 세 번째 예제처럼 대문자는 테이블의 범위를 벗어납니다.

자주 묻는 질문3

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

누락된 카운터 윈도우는 O(n + m) 시간에 실행되며, 여기서 n과 m은 s와 t의 길이입니다. 테이블을 만들 때 t를 한 번 읽고, s의 각 문자는 최대 한 번 윈도우에 들어갔다가 나옵니다. 추가 메모리는 문자 코드당 하나의 카운트입니다.

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

왼쪽 끝은 그 위치에서 시작하는 윈도우가 t를 포함한 뒤에만 해당 위치를 지나며, 그 윈도우는 그 시작점에서 조건을 만족하는 가장 짧은 윈도우였습니다. 그 위치에서 시작해 더 늦게 끝나는 윈도우는 모두 더 길기 때문에, 되돌아가도 더 나은 답을 찾을 수 없습니다.

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

애너그램은 t의 문자를 정확히 모두 포함하므로, 해당 윈도우의 길이는 m으로 고정되며 한 번에 한 단계씩 이동합니다. 여기서는 추가 문자가 허용되므로 길이도 답의 일부입니다. 윈도우는 t를 포함할 때까지 커지고, 계속 포함하는 동안 줄어듭니다.

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

테스트 #1

테스트 #2

테스트 #3

인자들

s = "mappingtheplan"
t = "nap"

예상 출력

"plan"

Minimum Window Substring

함수

제약 조건

예제

힌트

풀이

모든 시작 위치에서 윈도우를 확장합니다

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

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

함정과 경계 사례

자주 묻는 질문3

비슷한 문제