题解 | 最小覆盖子串

#include <climits>
#include <unordered_map>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    string minWindow(string S, string T) {
        // write code here
        int m = S.size();
        int n = T.size();
        string  res = "";
        int min_len = INT_MAX;
        unordered_map<char, int> u_map_need;
        unordered_map<char, int> u_map_window;
        for (const char& ch : T) u_map_need[ch]++;
        int need_max = u_map_need.size();
        int need_count = 0;
        for (const auto &[key, val] : u_map_need) u_map_window[key] = 0;

        int left = 0, right = 0;
        while (right < m) {
            char ch_tmp = S[right];
            if (u_map_window.count(ch_tmp)) {
                u_map_window[ch_tmp]++;
                if (u_map_window[ch_tmp] == u_map_need[ch_tmp]) need_count++;
            }
            right++;
            if (left < right && need_count == need_max) {
                while (left < right && need_count == need_max) {
                    char l_ch_tmp = S[left];
                    left++;
                    if (u_map_window.count(l_ch_tmp)) {
                        if (u_map_window[l_ch_tmp] == u_map_need[l_ch_tmp]) need_count--;
                        u_map_window[l_ch_tmp]--;
                    }
                }
                left--;
                if(right-left<min_len) {
                    min_len = right-left;
                    res = S.substr(left,min_len);      
                }
                left++;
            }
        }
        return res;
    }
};