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);
    }
};

/*
    0 1 2 3 4 5 6 7 8
S = a b c d e b d d e  T = b d e
              ^     ^              ^
              s      e


    ans = (4 - 1) + 1 = 4

*/