<p>Given two strings <code>s</code> and <code>t</code> of lengths <code>m</code> and <code>n</code> respectively, return <em>the <strong>minimum window</strong></em> <span data-keyword="substring-nonempty"><strong><em>substring</em></strong></span><em> of </em><code>s</code><em> such that every character in </em><code>t</code><em> (<strong>including duplicates</strong>) is included in the window</em>. If there is no such substring, return <em>the empty string </em><code>&quot;&quot;</code>.</p>

<p>The testcases will be generated such that the answer is <strong>unique</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;ADOBECODEBANC&quot;, t = &quot;ABC&quot;
<strong>Output:</strong> &quot;BANC&quot;
<strong>Explanation:</strong> The minimum window substring &quot;BANC&quot; includes &#39;A&#39;, &#39;B&#39;, and &#39;C&#39; from string t.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;a&quot;, t = &quot;a&quot;
<strong>Output:</strong> &quot;a&quot;
<strong>Explanation:</strong> The entire string s is the minimum window.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;a&quot;, t = &quot;aa&quot;
<strong>Output:</strong> &quot;&quot;
<strong>Explanation:</strong> Both &#39;a&#39;s from t must be included in the window.
Since the largest window of s only has one &#39;a&#39;, return empty string.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == s.length</code></li>
	<li><code>n == t.length</code></li>
	<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> and <code>t</code> consist of uppercase and lowercase English letters.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong> Could you find an algorithm that runs in <code>O(m + n)</code> time?</p>

class Solution {
public:
    pair<int, int> best;
    string s;
    string t;
    int goal_hist[128] = {};
    int curr_hist[128] = {};
    int i = 0;
    int j = 0;

    bool hist_valid() {
        for (int i = 0; i < 128; i++) {
            if (curr_hist[i] < goal_hist[i]) {
                return false;
            }
        }
        return true;
    }

    void inc_i() {
        char old_char = s[i];
        curr_hist[old_char]--;
        i++;
    }

    void dec_i() {
        i--;
        char old_char = s[i];
        curr_hist[old_char]++;
    }

    void inc_j() {
        char new_ch = s[j];
        j++;
        curr_hist[new_ch]++;
    }

    string minWindow(string _s, string _t) {
        s = _s;
        t = _t;
        best = { 0, s.size() + 1 };

        for (char ch : t) goal_hist[ch]++;

        while (true) {
            while (!hist_valid() && j <= s.size()) inc_j();
            if (j > s.size()) break;

            while (hist_valid()) inc_i();
    
            dec_i();
            if (j - i < best.second - best.first) {
                best = { i, j };
                // cout << s.substr(i, j - i) << '\n';
            }
            inc_i();

            if (j == s.size()) break;
        }

        if (hist_valid()) {
            if (j - i < best.second - best.first) {
                best = { i, j };
            }
        }
        
        if (best.second - best.first > s.size()) {
            return "";
        }

        return s.substr(best.first, best.second - best.first);
    }
};
10600