76. Minimum Window Substring

Leetcode link

题目简介

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */

题目给我们两个字符串 s 与 t

要求我们在 s 中找到包含 t 所有字符的最短子字符串

如果没有找到，则返回空字符串

要求时间复杂度是 O(m+n)，其中 m 与 n 分别代表 s 与 t 的字符串长度

解题思路

我们的思路是使用滑动窗口，需要两个指针 left 与 right，我们使用 s = "ADOBECODEBANC", t = "ABC" 作为例子

1. 初始化：left = right = 0
2. 移动 right 指针直到包含所有 t 中的字符，此时 left = 0, right = 5，子字符串为 'ADOBEC'
3. 将 left 向右移动，直到遇到第一个在 t 中的字符，在这个例子中 left 不需要移动
4. 我们记录当前的子字符串下标 [0, 5]
5. 将 left 向右移动，直到越过第一个在 t 中的字符，此时 left = 1，子字符串为 'DOBEC'
6. 重复步骤 2，继续移动 right，直到找到下一个符合条件的子字符串，此时 left = 1, right = 10，子字符串为 'DOBECODEBA'
7. 重复步骤 3，left 移动至 3，此时 left = 3, right = 10，字符串为 'BECODEBA'
8. 重复步骤 4，由于当前范围 [3, 10] 比 [0, 5] 大，所以维持原纪录
9. （以此类推）

Javascript

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
    if (s.length < t.length) {
        return ''
    }

    // {targetChar: count}
    const map = new Map()
    for (const char of t) {
        map.set(char, (map.get(char) || 0) + 1)
    }
    let remainingChars = t.length

    const window = [0, Number.MAX_SAFE_INTEGER]
    let left = 0

    for (let right = 0; right < s.length; right++) {
        const char = s[right]
        if (map.has(char) && map.get(char) > 0) {
            remainingChars--
        }
        // handle redundant char which is in t
        if (map.has(char)) {
            map.set(char, map.get(char) - 1)
        }

        if (remainingChars === 0) {
            while (true) {
                const leftChar = s[left]
                if (map.has(leftChar) && map.get(leftChar) === 0) {
                    // we find the leftmost char which is in t

                    // update window
                    if (window[1] - window[0] > right - left) {
                        window[0] = left
                        window[1] = right
                    }

                    // update map and remainingChars
                    remainingChars++
                    map.set(leftChar, 1)
                    left++
                    break
                }
                // handle redundant char which is in t
                if(map.has(leftChar)) {
                    map.set(leftChar, map.get(leftChar) + 1)
                }
                left++
            }
        }
    }

    return window[1] >= s.length ? '' : s.slice(window[0], window[1] + 1)
};