【LeetCode】76. Minimum Window Substring(C++)

アドレス:https://leetcode.com/problems/minimum-window-substring/
タイトル:
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O ( n ) O(n) O(n).
Example:
Input: S = “ADOBECODEBANC”, T = “ABC” Output: “BANC”
Note:

If there is no such window in S that covers all characters in T, return the empty string "" .

If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

理解:
Sの最も短いサブストリングを求めて、それがTを含むようにします
実装:
スライドウィンドウの考え方を使う.Tが出現した文字の回数を1つのmapで最初に記録する.Sの現在の文字がTにある場合、mapからカウントを1つ減算します.counterが0より大きいと、現在のサブ列にTの文字列が完全に含まれていないことを示します.スライドウィンドウのサイズを小さくするには、サブストリングにTが含まれていない場合にcounterを変更するだけでよいことに注意してください.mapのvalueが0に等しい場合、このとき1を0より大きくすると、ウィンドウにTが含まれないことを示します.最初にcounterをT.size()に初期化するのも巧みですが、実は最後までcounterはせいぜい1です.

class Solution {
public:
	string minWindow(string s, string t) {
		unordered_map<char, int> map;
		for (auto c : t)
			map[c]++;
		int counter = t.size(), l = 0, r = 0, d = INT_MAX, head = 0;
		while (r < s.length()) {
			char rc = s[r++];
			if (map.count(rc)) {
				if (map[rc]-- > 0)
					counter--;
			}
			while (counter == 0) {
				if (r - l < d) d = r - (head = l);
				char lc = s[l++];
				if (map.count(lc)) {
					if (map[lc]++ == 0)
						counter++;	
				}
			}				
		}
		return d == INT_MAX ? "" : s.substr(head, d);
	}
};