[LeetCode] 76. Minimum Window Substring

슬라이딩 윈도우를 구현하여 쉽게 풀이할 수 있는 문제이다.

중요 포인트는 각 윈도우 별 스펠링의 수를 대조하여 최소 길이의 윈도우를 찾아내는 것이 중요하다.

처음에는 고정된 윈도우 길이를 한칸씩 이동하며 검증하는 방식을 사용했으나, 시간 초과가 발생하여 우측 포인터를 미리 이동하고 좌측 포인터를 검증하며 따라가는 방식으로 변경하였음

😎풀이

function minWindow(s: string, t: string): string {
    const m = s.length
    const n = t.length
    if (n > m) return ""

    const tMap = new Map<string, number>()
    for (const char of t) {
        tMap.set(char, (tMap.get(char) || 0) + 1)
    }

    let left = 0, right = 0
    let required = tMap.size // t에 있는 고유 문자 수
    let formed = 0 // 현재 윈도우에 포함된 t문자 수
    const windowCounts = new Map<string, number>()
    let minLength = Infinity
    let minLeft = 0

    while (right < m) {
        const char = s[right]
        windowCounts.set(char, (windowCounts.get(char) || 0) + 1)

        if (tMap.has(char) && windowCounts.get(char) === tMap.get(char)) {
            formed++;
        }

        while (left <= right && formed === required) {
            const charLeft = s[left]
            // 현재 윈도우 길이가 최소 길이보다 짧으면 업데이트
            if (right - left + 1 < minLength) {
                minLength = right - left + 1
                minLeft = left
            }

            // 왼쪽 문자를 윈도우에서 제거
            windowCounts.set(charLeft, windowCounts.get(charLeft) - 1);
            // t에 있는 문자이고, 현재 윈도우에서 필요한 수보다 적어지면 formed 감소
            if (tMap.has(charLeft) && windowCounts.get(charLeft) < tMap.get(charLeft)) {
                formed--;
            }

            left++
        }

        right++
    }

    // 최소 길이가 초기값이라면 빈 문자열 반환, 그렇지 않으면 최소 윈도우 반환
    return minLength === Infinity ? "" : s.slice(minLeft, minLeft + minLength);
}