76-最小覆盖子串

LeetCode 76. Minimum Window Substring

LeetCode-76

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”.

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

method

滑动窗口：当滑动窗口内的子串频数等于t串的频数时就可以记录结果

窗口范围：[left, right)

1. 窗口右端点一直往右移，频数增加，直到满足条件
2. 窗口左端点尝试往左移，试图减小窗口范围，当不满足频数条件返回步骤1

sCount只记录需要的频数就可以了，t串只有abc，sCount也只记录abc的频数

unordered_map<char, int> sCount, tCount;
bool check() {
    for (auto t : tCount) {
        if (sCount[t.first] < t.second) {
            return false;   // 不满足直接返回
        }
    }
    return true;
}
string minWindow(string s, string t) {
    for (auto c : t) {
        tCount[c]++;    // 计算t串的频数
    }
    int l = 0;   // [l, i]
    int len = INT_MAX;  // 结果长度
    int pos = -1;      // 结果左端点
    while (int i = 0; i < s.size(); i++) {
        if (tCount.count(s[i])) {    // s[i]在t串中
            sCount[s[i]]++; // 右端点右移，频数增加
        }
        while (check() && l <= i) {
            if (i - l + 1 < res) {
                len = i - l + 1;    // 更新子串长度
                pos = l;   // 更新左端点
            }
            if (tCount.count(s[l])) {    // s[l]在t串中
                sCount[s[l]]--; // 左端点要往右移，频数要减少
            }
            l++;    // 要放在外面，左端点一直右移
        }
    }
    return pos == -1 ? "" : s.substr(pos, len);
}

因为只包含字母，就可以用数组来作哈希表，同时用distance来表明窗口字符串是否包含t串

distance表示滑动窗口内的字母与t中字母的接近程度，窗口内单个字母个数等于t中对应的字母个数时不再增加

• 当右端点向右移动时，只有当right指向字母的频数小于t中字母的频数时才distance+1，等于不再增加
• 当distance == t.size()时，表明窗口中的元素包含了t中的所有元素
• 当左端点向右移动时，要移除left指向的元素，所以left指向的字母的频数等于t中对应字母的频数时才distance-1

string minWindow(string s, string t) {
    int sCount[128] = {0};  // ascii(z)=122
    int tCount[128] = {0};  // 所以开128足够了
    for (auto c : t) {
        tCount[c]++;    // 记录t中频数
    }
    int l = 0;
    int len = INT_MAX;
    int pos = -1;
    int distance = 0;
    for (int i = 0; i < s.size(); i++) {
        if (sCount[s[i]] < tCount[s[i]]) {
            distance++;     // 小于才增加distance
        }
        sCount[s[i]]++;     // 频数一样累加
        while (distance == t.size()) {  // 等于就是包含了
            if (i - l + 1 < len) {
                len = i - l + 1;
                pos = l;   // 一样更新结果
            }
            if (sCount[s[l]] == tCount[s[l]]) {
                distance--; // 等于才减少distance
            }
            sCount[s[l]]--; // 频数减少
            l++;
        }
    }
    return pos == -1 ? "" : s.substr(pos, len);
}