76. Min Window Substring

滑动窗口的题目 基本有个共同特徵

一旦left_idx和right_idx达成某种条件时

我们先计算窗口长度right_idx + 1 - left_idx

和历史最大或最小窗口长度比较 更新历史纪录

有时甚至还得记载窗口的起始索引

然后把left_idx往右移动

直到不满足某种条件 或者left_idx > right_idx为止

Minimum Window Substring

今天来拿第76号难题做示范

给了我们source_str和target_str俩字串

(其实题目里是叫s和t 但source_str和target_str更有可读性)

要求在source_str中找到一个最短的子串

这子串要包含target_str里所有出现的字符 重复的也要覆盖到

找不到的话 就返回空字符串

老朋友哈希表🔢

得先统计下target_str里每个字符出现的次数

因为这是题目指定得 包含重复情形 全数覆盖 的对象

这表就叫做tgt_chars_counts

同时我们先为接下来准备两变量：

1. min_len：历史最短窗口长度 初始值为len(source_str) + 1 象徵还没找到符合子串
2. min_left_idx：历史最短窗口的left_idx 初始值为-1

就当做在买保险：少买不行 多买没关系

一、right_idx总是在右移

开个整数变量unique_tgt_chars_coverage

追踪当前窗口 覆盖多少种『Unique』的target_str字符

每次我们把right_idx往右移动时

当下的source_str[right_idx] 姑且叫做char

先看char是不是tgt_chars_counts的键

唯有是 这char才是我们要覆盖的对象

如果确实是 tgt_chars_counts[char]减1

象徵我们给这个char又买了一份保险

要是tgt_chars_counts[char]给减到0了

就说明char的覆盖要求彻底达成啦

于是在此刻 unique_tgt_chars_coverage加1

这边有个关键是 哪怕我们已达成对char的彻底覆盖

只要又有遇到char 那么tgt_chars_counts[char]仍要继续减1

掉到负数并没关系 因为这说明我们是 超额覆盖

超额覆盖是没有犯规的

没把unique_tgt_chars_coverage重复加1就好😏

因此只有减到0那瞬间 才能升高覆盖计数

二、left_idx何时能右移

unique_tgt_chars_coverage一旦打平len(tgt_chars_counts)时

意味著咱们当前窗口完全覆盖target_str里所有的字符

赶快先计算当前窗口长度window_len = right_idx + 1 - left_idx

拿去和min_len比较 若成了历史新高

还要连带用left_idx更新min_window_left_idx

毕竟最后我们要回去切source_str的子串作为答案

记录检查更新弄好后 left_idx就能往右移啰

因此会出现一个掉出窗口的字符

也就是source_str[left_idx] 姑且叫做removed_char了

同样地 先看removed_char是不是tgt_chars_counts的键

唯有是 这removed_char才是我们要覆盖的对象

如果确实是 tgt_chars_counts[removed_char]加1

象徵我们给这个removed_char退掉了一份保险

要是tgt_chars_counts[removed_char]变成大于0的瞬间

就说明本来彻底覆盖的removed_char现在露馅咯

于是此刻unique_tgt_chars_coverage必须减1

就像第一段的逻辑 哪怕removed_char已有露馅行为

只要又有removed_char流失 tgt_chars_counts[removed_char]仍要继续加1

因为这说明我们是 露馅越来越严重

后面需要好好捕回来才能做到覆盖要求

只要没把unique_tgt_chars_coverage重复减1就好😏

tgt_chars_counts[removed_char]从0变大于0那瞬间 才要调低覆盖计数

最后等窗口全部扫描完毕 看min_len是否等于len(source_str) + 1

是的话 代表根本没找到符合条件的子串 必须回传""

否则就回传source_str[min_window_left_idx: min_window_left_idx + min_len]

C++

#include <string>
#include <unordered_map>
using namespace std;

string findMinWindowSubstring(string sourceString, string targetString) // LeetCode Q.76.
{
    unordered_map<char, int> tgtCharsCounts;

    for (const auto& character : targetString)
        tgtCharsCounts[character]++;

    int uniqueTgtCharsCount = tgtCharsCounts.size();

    // Must not exceed unique target chars count during sliding window.
    int uniqueTgtCharsCoverage = 0;

    int minWindowLeftIdx = -1;
    int minLen = sourceString.size() + 1; // Source length + 1: symbol of not found yet.

    int leftIdx = 0;
    for (int rightIdx = 0; rightIdx < sourceString.size(); rightIdx++) {
        char character = sourceString[rightIdx];
        if (tgtCharsCounts.find(character) != tgtCharsCounts.end()) {
            tgtCharsCounts[character]--;

            if (tgtCharsCounts[character] == 0) // Becomes covered.
                uniqueTgtCharsCoverage++;
        }

        while (uniqueTgtCharsCoverage == uniqueTgtCharsCount) // Can shrink window.
        {
            int windowLen = rightIdx + 1 - leftIdx;

            if (windowLen < minLen)
                minLen = windowLen, minWindowLeftIdx = leftIdx;

            char removedChar = sourceString[leftIdx];
            if (tgtCharsCounts.find(removedChar) != tgtCharsCounts.end()) {
                tgtCharsCounts[removedChar]++;

                if (tgtCharsCounts[removedChar] > 0) // Becomes uncovered.
                    uniqueTgtCharsCoverage--;
            }

            leftIdx += 1;
        }
    }

    if (minLen == sourceString.size() + 1)
        return "";

    return sourceString.substr(minWindowLeftIdx, minLen);
}

Python

def find_min_window_substring(source_str: str, target_str: str) -> str:  # LeetCode Q.76.
    tgt_chars_counts: dict[str, int] = dict()

    for char in target_str:
        if char not in tgt_chars_counts.keys():
            tgt_chars_counts.update({char: 0})
        tgt_chars_counts[char] += 1

    unique_tgt_chars_count = len(tgt_chars_counts)

    # Must not exceed unique target chars count during sliding window.
    unique_tgt_chars_coverage = 0

    min_window_left_idx = -1
    min_len = len(source_str) + 1  # Source length + 1: symbol of not found yet.

    left_idx = 0
    for right_idx, char in enumerate(source_str):
        if char in tgt_chars_counts.keys():
            tgt_chars_counts[char] -= 1

            if tgt_chars_counts[char] == 0:  # Becomes covered.
                unique_tgt_chars_coverage += 1

        while unique_tgt_chars_coverage == unique_tgt_chars_count:  # Can shrink window.
            window_len = right_idx + 1 - left_idx

            if window_len < min_len:
                min_len = window_len
                min_window_left_idx = left_idx

            removed_char = source_str[left_idx]
            if removed_char in tgt_chars_counts.keys():
                tgt_chars_counts[removed_char] += 1

                if tgt_chars_counts[removed_char] > 0:  # Becomes uncovered.
                    unique_tgt_chars_coverage -= 1

            left_idx += 1

    if min_len == len(source_str) + 1: return ""

    return source_str[min_window_left_idx: min_window_left_idx + min_len]

时间复杂度：O(|\text{source_str}| + |\text{target_str}|)

空间复杂度：O(|\text{target_str}|)