<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>

#define maxn 100010
#define count _count

class Solution {
public:
    int S[maxn], T[maxn], count[130], cur_count[130], is_full[130];
    int n, m;
    string minWindow(string s, string t) {
        n= s.length();
        m= t.length();
        for (int i=0; i<n; i++) S[i+1]= s[i]-'a'+60;
        for (int i=0; i<m; i++) T[i+1]= t[i]-'a'+60;
       // for (int i=1; i<=m; i++) cout<<T[i]<<" ";
      //  cout<<endl;
        for (int i=0; i<130; i++) count[i]=0;
        for (int i=1; i<=m; i++) count[T[i]]++;
        for (int i=0; i<130; i++) cur_count[i]=is_full[i]=0;
        cur_count[S[1]]++; 
        int is_filled=0;
        for (int i=0; i<130; i++) if (cur_count[i]>=count[i]) is_filled++;
        int L=1, R=1;
        int ans=1000000, index_L= -1, index_R= 1000000000;
        while(1){
            if (is_filled==130){
                if (R-L<=index_R-index_L){
                    index_L=L;
                    index_R=R;
                }
                cur_count[S[L]]--;
                if (cur_count[S[L]]<count[S[L]]) is_filled--;
                L++;
            }
            else{
                R++;
                if (R>n) break;
                cur_count[S[R]]++;
                if (cur_count[S[R]]==count[S[R]]) is_filled++;
            }

        }
        if (index_L==-1) return "";
        string output= "";
        for (int i=index_L; i<=index_R; i++) output+=s[i-1];
        return output;
    }
};


10600