727. Minimum Window Subsequence

    string minWindow(string S, string T) {
        int NS = S.size(), NT = T.size();
        vector<vector<int>> dp(NT, vector<int> (NS, -1));
        string res;
        for(int i=0; i<NT; i++) {
            for(int j=i; j<NS; j++) {
                if(T[i] == S[j]) {
                    if(i == 0)
                        dp[i][j] = j;
                    else {
                        dp[i][j] = dp[i-1][j-1];
                    }
                    if(i == NT - 1 && dp[i][j] != -1){
                        string s = S.substr(dp[i][j], j - dp[i][j] + 1);
                        if(res.empty()) res = s;
                        else if(s.size() < res.size()) res = s;
                    }
                }
                else if(j>0){
                    dp[i][j] = dp[i][j-1];
                }
                if(j == NS-1 && dp[i][j] == -1) return "";
            }
        }
        return res;
    }