Minimum Window Substring Solutions in C++

// Source : https://oj.leetcode.com/problems/minimum-window-substring/
// Author : Hao Chen
// Date   : 2014-07-22



#include <string.h>
#include <iostream>
#include <string>
using namespace std;

#define INT_MAX      2147483647

string minWindow(string s, string t) {
    string win;
    if (s.size()<=0 || t.size()<=0 || t.size() > s.size()) return win;
    /*
     * Declare two "hash map" for ASCII chars
     *   window[]: represents the char found in string S
     *   dict[]: stores the chars in string T
     */    
    const int MAX_CHARS = 256;
    int window[MAX_CHARS], dict[MAX_CHARS];

    const int NOT_EXISTED   = -1;
    const int NOT_FOUND     =  0;
    memset(dict, NOT_EXISTED, sizeof(dict));
    memset(window, NOT_EXISTED, sizeof(window));

    /* 
     *  Go through the T, and inital the dict[] and window[] 
     *  Notes: a same char can be appeared multiple times.
     */
    for(int i=0; i<t.size(); i++) {
        dict[t[i]]==NOT_EXISTED ? dict[t[i]]=1 : dict[t[i]]++ ; 
        window[t[i]] = NOT_FOUND; 
    }

    int start =-1;
    int winSize = INT_MAX;
    int letterFound = 0;
    int left = 0;

    for(int right=0; right<s.size(); right++) {
        if ( dict[s[right]] == NOT_EXISTED ){
            continue;
        }

        /* if s[i] is existed in `t` */ 
        char chr = s[right];
        window[chr]++;

        /* if one char has been found enough times, then do not do letterFound++ */
        if (window[chr] <= dict[chr]) {
            letterFound++;
        }

        if ( letterFound >= t.size() ) {
            /* 
             * Find the left of the window - try to make the window smaller
             * 1) windows[S[left]] == NOT_EXISTED  ===> the char at the `left` is not in T
             * 2) window[S[left]] > dict[S[left]]   ===> a same char appeared more than excepted.
             */
            char chl = s[left];
            while ( window[chl] == NOT_EXISTED || window[chl] > dict[chl] ) { 
                if (dict[chl] != NOT_EXISTED  ) {
                    //move the left of window
                    window[chl]--; 
                    // reduce the number of letters found
                    if (window[chl] < dict[chl] ) letterFound--;
                }
                chl = s[++left];
            }

            /* Calculate the minimized window size */
            if(winSize > right - left + 1){
                start = left;
                winSize = right - left + 1;
            }

        }
    }

    if (start>=0 && winSize>0) {
        win = s.substr(start, winSize);
    }
    return win;
}

int main(int argc, char**argv)
{
    string S = "ADOBECODEBANC";
    string T = "ABC";
    if (argc>2){
        S = argv[1];
        T = argv[2];
    }
    cout << "S = \"" << S << "\"  T=\"" << T << "\"" <<endl;
    cout << minWindow(S, T) << endl;
    return 0;
}

/// Source : https://leetcode.com/problems/minimum-window-substring/
/// Author : liuyubobobo
/// Time   : 2017-01-17

#include <iostream>
#include <cassert>

using namespace std;

/// Sliding Window
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    string minWindow(string s, string t) {

        int tFreq[256] = {0};
        for(int i = 0 ; i < t.size() ; i ++)
            tFreq[t[i]] ++;

        int sFreq[256] = {0};
        int sCnt = 0;

        int minLength = s.size() + 1;
        int startIndex = -1;

        int l = 0, r = -1;
        while(l < s.size()){

            if(r + 1 < s.size() && sCnt < t.size()){

                sFreq[s[r+1]] ++;
                if(sFreq[s[r+1]] <= tFreq[s[r+1]])
                    sCnt ++;
                r ++;
            }
            else{
                assert(sCnt <= t.size());
                if(sCnt == t.size() && r - l + 1 < minLength){
                    minLength = r - l + 1;
                    startIndex = l;
                }

                sFreq[s[l]] --;
                if(sFreq[s[l]] < tFreq[s[l]])
                    sCnt --;
                l ++;
            }
        }

        if( startIndex != -1 )
            return s.substr(startIndex, minLength);

        return "";
    }
};

int main() {

    cout << Solution().minWindow("ADOBECODEBANC", "ABC") << endl;
    // BANC

    cout << Solution().minWindow("a", "aa") << endl;
    // empty

    cout << Solution().minWindow("aa", "aa") << endl;
    // aa

    cout << Solution().minWindow("bba", "ab") << endl;
    // ba

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-window-substring/
/// Author : liuyubobobo
/// Time   : 2018-08-28

#include <iostream>
#include <cassert>
#include <unordered_set>
#include <vector>

using namespace std;

/// Sliding Window
/// Using filtered s, which remove all characters not in T
/// will be a good improvement when T is small and lots of character are not in S:)
///
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    string minWindow(string s, string t) {

        unordered_set<char> t_set;
        int tFreq[256] = {0};
        for(char c: t){
            t_set.insert(c);
            tFreq[c] ++;
        }

        string filtered_s = "";
        vector<int> pos;
        for(int i = 0; i < s.size() ; i ++)
            if(t_set.find(s[i]) != t_set.end()){
                filtered_s += s[i];
                pos.push_back(i);
            }


        int sFreq[256] = {0};
        int sCnt = 0;

        int minLength = s.size() + 1;
        int startIndex = -1;

        int l = 0, r = -1;
        while(l < filtered_s.size()){

            if(r + 1 < filtered_s.size() && sCnt < t.size()){

                sFreq[filtered_s[r+1]] ++;
                if(sFreq[filtered_s[r+1]] <= tFreq[filtered_s[r+1]])
                    sCnt ++;
                r ++;
            }
            else{
                assert(sCnt <= t.size());
                if(sCnt == t.size() && pos[r] - pos[l] + 1 < minLength){
                    minLength = pos[r] - pos[l] + 1;
                    startIndex = pos[l];
                }

                sFreq[filtered_s[l]] --;
                if(sFreq[filtered_s[l]] < tFreq[filtered_s[l]])
                    sCnt --;
                l ++;
            }
        }

        if( startIndex != -1 )
            return s.substr(startIndex, minLength);

        return "";
    }
};


int main() {

    cout << Solution().minWindow("ADOBECODEBANC", "ABC") << endl;
    // BANC

    cout << Solution().minWindow("a", "aa") << endl;
    // empty

    cout << Solution().minWindow("aa", "aa") << endl;
    // aa

    cout << Solution().minWindow("bba", "ab") << endl;
    // ba

    return 0;
}