Description

Submission

class Solution {
public:
    string minWindow(string s1, string s2) {
        int n = s1.length();
        int m = s2.length();
        s1 = '#' + s1;

        int states[26][n+1];

        for(int i = 0; i < 26; ++i) {
            states[i][n] = -1;
        }

        for(int i = n-1; i >= 0; --i) {
            for(int k = 0; k < 26; ++k) {
                states[k][i] = states[k][i+1]; 
            }
            states[s1[i+1]-'a'][i] = i + 1;
        }

        int minLen = INT_MAX;
        int retFirst = 0;
        int cur = 0;
        while(cur <= n) {
            int first = states[s2[0]-'a'][cur];
            if(first == -1) break;
            
            for(int j = 0; j < m; ++j) {
                cur = states[s2[j]-'a'][cur];
                if(cur == -1) break;
            }

            if(cur == -1) break;
            int len = cur - first + 1;
            
            if(minLen > len) {
                minLen = len;
                retFirst = first;
            }
            cur = first;
        }

        if(minLen == INT_MAX) return "";
        return s1.substr(retFirst, minLen);
    }
};