class Solution {
public:
    string minWindow(string S, string T) {

        vector <int> starts;
        int res_len = INT_MAX;
        int res_s = INT_MAX;
        for (int i= 0 ; i < S.size(); i++)
        {
            if (S[i] == T[0])
                starts.push_back(i);
        }


        for (int i = 0 ; i < starts.size(); i++)
        {
            int s = starts[i];
            int e = s + 1;
            int t = 1;

            for ( ; e < S.size() && t < T.size();)
            {
                if (S[e] == T[t])
                    t++;
                e++;
            }
            if (t != T.size())
                continue;

            if (e - s < res_len)
            {
                res_len = e - s ;
                res_s = s;
            }

        }
        return res_len == INT_MAX ? "":S.substr(res_s,res_len);
    }
};

O(S*T)

class Solution {
public:
    string minWindow(string S, string T) {

        vector <int> starts;
        vector<int> chars(26, -1);
        vector<vector<int>> nxtX(S.size());
        for(int i = S.size()-1; i >= 0; i--) {
            chars[S[i]-'a'] = i;
            nxtX[i] = chars;
        }

        int res_len = INT_MAX;
        int res_s = INT_MAX;
        for (int i= 0 ; i < S.size(); i++)
        {
            if (S[i] == T[0])
                starts.push_back(i);
        }


        for (int i = 0 ; i < starts.size(); i++)
        {
            int s = starts[i];
            int e = s + 1;
            int t = 1;
                for ( ; e < S.size() && t < T.size();)
                {
                    e = nxtX[e][T[t]-'a'];
                    if(!~e) break;
                    t++;
                    e++;
                }

            if (t != T.size())
                continue;

            if (e - s < res_len)
            {
                res_len = e - s ;
                res_s = s;
            }

        }
        return res_len == INT_MAX ? "":S.substr(res_s,res_len);
    }
};

class Solution {
public:
    string minWindow(string S, string T) {

        vector < vector <int> > dp (S.size(), vector <int> (T.size(), -1));

        for (int i = 0 ; i < S.size(); i++)
        {
            if (S[i]== T[0])
            {
                dp[i][0] = i;
            }
        }
        int res_len = INT_MAX;
        int res_start = -1;

        for (int i = 1; i < T.size(); i++)
        {
            int start = -1;
            for (int j = 0 ; j < S.size(); j++)
            {
                if (S[j] == T[i])
                {
                    dp[j][i] = start;
                }

                start = max (start, dp[j][i - 1]);

            }
        }

        int l = T.size() - 1;
        for (int j = 0 ; j  < S.size(); j++)
        {
            if (dp[j][l] != -1  && (j - dp[j][l] + 1  < res_len))
                {
                    res_len = j - dp[j][l] + 1 ;
                    res_start = dp[j][l];
                }
        }

        return res_start == -1 ? "" : S.substr(res_start, res_len);
    }

O(S*T
};