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

// strings 
//    s - length m - bigger string
//    t - length n
// Return minimum window substring of s (return the substring) such that 
// every char in t (including duplicates) is included. 
// - Does order matter?
// 
// Example:
//     s - ADOBECODEBANC
//     t - ABC 
// 
// Hashtable to track how many instances of letter were found:
//  - When all combination of letters found - store as window (begin, end indices) if it's min length
//  - Algo -
//  - Go through s - 
//     - if element found in hashtable of t, increment/decrement that element
//     - if all elements -> 0 (keep checking or use hashset for optimization), store begin, end as min. Init to negative number. Increment if seen. 
//     - Left, right pointers for window
//        - If elements -> 0, move left pointer until next letter in t found (how to optimize?). -1 to char that was removed. 
//        - Keep moving right pointer, repeating step 1.
//        - move both left and right until first letter found
//        - Mid of seq - don't move left pointer 
//                     - keep moving right
//                     - #1, #2




// ADOBECODEBANC
// L    R 
//    L      R 
//      L    R
//          LR
//      
// ABC 


class Solution {
public:

    uint getAbsIndex(char letter)
    {
        uint offsetindex = 0;
        uint absindex = 0;

        if (letter >= 'a' && letter <= 'z')
        {
            offsetindex = 0;
            absindex = offsetindex + letter - 'a';
        } else 
        {
            offsetindex = 26;
            absindex = offsetindex + letter - 'A';
        }

        return absindex;
    }

    void incrementDecrementLetter(int *lettercounts, bool increment, char letter)
    {        
        lettercounts[getAbsIndex(letter)] += (increment ? 1 : -1);
    }

    bool checkZero(int *lettercounts, char letter)
    {
        return(lettercounts[getAbsIndex(letter)] == 0);
    }

    bool checkNegative(int *lettercounts, char letter)
    {
        return(lettercounts[getAbsIndex(letter)] < 0);
    }

    class BitSet
    {
        long bitfield;

    public:
        
        BitSet()
        {
            bitfield = 0;
        }

        void insert(char letter)
        {
            bitfield |= ((long) 1 << getAbsIndex(letter));        
        }

        void erase(char letter)
        {
            bitfield &=  ~((long) 1 << getAbsIndex(letter));
        }

        bool exists(char letter)
        {
            return((((long) 1 << getAbsIndex(letter)) & bitfield) != 0);
        }

        bool isempty()
        {
            return(bitfield == 0);
        }

    private:
        long getAbsIndex(char letter)
        {
            long offsetindex = 0;
            long absindex = 0;

            if (letter >= 'a' && letter <= 'z')
            {
                offsetindex = 0;
                absindex = offsetindex + letter - 'a';
            } else 
            {
                offsetindex = 26;
                absindex = offsetindex + letter - 'A';
            }

            return absindex;
        }
    };


    string minWindow(string s, string t) {
        
        uint countpossibleletters = ('Z'-'A'+1) + ('z'-'a'+1);
        BitSet allletters;   
        BitSet lettersremaining;
        long lindex = 0;
        long rindex = 0;
        long lminwindow = 0;
        long rminwindow = s.length()-1;
        long minwindowpossible = t.length();
        bool inwindow = false;
        bool matchfound = false;

        int* lettercounts = new int[countpossibleletters]();

        

        if (s.length() == 0 || t.length() == 0)
        {
            return "";
        }

        for (int i=0; i < t.length(); i++)
        {
            char test = t.at(i);
            
            incrementDecrementLetter(lettercounts, false, test);            
            allletters.insert(test);
            lettersremaining.insert(test);                      
        }

        while (rindex < s.length())
        {           
            if (allletters.exists(s.at(rindex)))
            {
                inwindow = true;
                incrementDecrementLetter(lettercounts, true, s.at(rindex));
                
                // Satisfied this character, check if all other letters satisfied - then it's window
                if (checkZero(lettercounts, s.at(rindex)))
                {
                    lettersremaining.erase(s.at(rindex));
                    if (lettersremaining.isempty())
                    {
                        matchfound = true;
                    

                        // Window update                        
                        if (rindex - lindex + 1 == minwindowpossible) 
                        {
                            return s.substr(lindex, minwindowpossible);
                        }

                        if ((rindex - lindex + 1) < (rminwindow - lminwindow + 1))
                        {
                            lminwindow = lindex;
                            rminwindow = rindex;
                        }

                        // Move left index until some char in map found - don't count it again - decrement the letter we advanced beyond
                        // Optimize???***
                        incrementDecrementLetter(lettercounts, false, s.at(lindex));
                        if (checkNegative(lettercounts, s.at(lindex))) 
                        {
                            lettersremaining.insert(s.at(lindex));
                        }

                        while(++lindex < rindex && !allletters.exists(s.at(lindex)))
                        {                            
                        }
                        
                        // Decrement letter counts at rindex to avoid double counting
                        incrementDecrementLetter(lettercounts, false, s.at(rindex));
                        lettersremaining.insert(s.at(rindex));
                        --rindex;
                    }
                }
            } else if (!inwindow)
            {
                ++lindex;
            } 

            ++rindex;
        }


        return (matchfound ? s.substr(lminwindow, rminwindow - lminwindow + 1) : "");
    }
};
9500