[LeetCode][Hard] 76. Minimum Window Substring

Leetcode 網址: https://leetcode.com/problems/minimum-window-substring/

題目說明:

給定一個字串 s 以及一個字串序列 t，

請在字串 s 中找出包含所有 t 出現的字元所需要的最短字串長度。

備註: 題目保證最短字串長度會是 unique 的。

Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Example 2:
Input: s = "a", t = "a"
Output: "a"

解題說明:

觀察題目敘述很直覺可以發現是 Sliding Window 的題目，

我們觀察 Example 看如何先找出單一個包含字串 t 的答案 (先不管最短) ~

1. 訪問 A 發現 A 是需要的字元，由於是第一個出現的需要字元所以 start 紀錄成 0；需要字元剩餘 2

2. 訪問 D 發現 D 不是需要的字元，繼續往下走；需要字元剩餘 2

3. 訪問 O 發現 O 不是需要的字元，繼續往下走；需要字元剩餘 2

4. 訪問 B 發現 B 是需要的字元，由於還欠缺其他字元所以繼續往下走；需要字元剩餘 1

5. 訪問 E 發現 E 不是需要的字元，繼續往下走；需要字元剩餘 1

6. 訪問 C 發現 C 是需要的字元，找到所有字元所以記錄這個答案 ADOBEC

以上是找出非最短的算法，接著我們要思考如何從這組算法找出下一組答案 ~

很直覺可以發現若找出一組比 ADOBEC 更短的答案，那勢必得捨去 A (也就是移除字串 ADO)，

所以捨去 ADO 之後將 Start 設成下一個需要的字元 B (index = 3)，

又由於我們只有捨棄 A，所以只要從 C 開始往後找找出下一個 A 就會是下一組可能更短的答案，

將以上的想法寫成 for loop 並判斷長度就可以找出答案了。

程式碼

class Solution {
public:
    string minWindow(string s, string t) {
        int minStart = 0, minLength = 0;
        int n = t.length(), required[256] = {0}, current[256] = {0}, start = -1, end = 0;
        for (int i = 0; i < t.length(); i++) required[t[i]]++;
        while (end < s.length()) {
            int c = s[end++];
            if (required[c] == 0) continue;
            start = start >= 0 ? start : end - 1;
            if (required[c] > current[c]++) n--;
            if (required[c] < current[c] && c == s[start]) 
                while (start < s.length() && !required[s[start]]) start++;
            while (n == 0) {
                if (minLength == 0 || minLength > end - start) {
                    minStart = start, minLength = end - start;
                }
                if (required[s[start]] > --current[s[start]]) n++;
                while (start < s.length() && !required[s[++start]]);
            }
        }
        return s.substr(minStart, minLength);
    }
};

結果

Runtime: 4 ms, faster than 99.26% of C++ online submissions for Minimum Window Substring.

Memory Usage: 7.3 MB, less than 99.85% of C++ online submissions for Minimum Window Substring.