O(S.size() * T.size()) C++ solution


  • 0
    M

    First let's tackle down the same problem but with no duplicates in string T. O(n^2) can be achieved by computing for each index i of S, the shortest substring starting at index i which sequentially covers the string T.

    This algorithm can be improved by reusing the computation of the earliest occurrences of characters. For example, when processing the ith character of S, if it's the jth character in T, we update the most recent occurrence of that character to i. The shortest substring ending at i which sequentially covers the first j characters consists of the shortest substring ending at the most recent occurrence of the first j-1 keywords plus the distance from the most recent occurrence of the (j-1)th character to i. The running time is O(S.size()).

    Since there may be duplicates in T, each character in T may correspond to several locations. As a result, when reaching a character in S that also appears in T, we need to update all data corresponding that character. Potentially, all characters in T are the same, then O(T.size()) updates every time. Total running time is O(S.size() * T.size()).

    class Solution {
    public:
        string minWindow(string S, string T) {
            int start_idx = -1, min_len = numeric_limits<int>::max();
            vector<int> last_occur(T.size(), -1);
            vector<int> leasts(T.size(), -1);
            unordered_map<char, vector<int>> mmap;
            
            for (int i=0; i<T.size(); i++)
                mmap[T[i]].push_back(i);
            
            for (int i=0; i<S.size(); i++) {
                if (mmap.find(S[i]) != mmap.end()) {
                    for (int j=mmap[S[i]].size()-1; j>=0; j--) { // start from back of the vector, otherwise if S="ab", T="aa", it'll fail
                        int pos = mmap[S[i]][j];
                        if (pos == 0) {
                            leasts[pos] = 1;
                        }
                        else if (leasts[pos-1] != -1) {
                            leasts[pos] = i - last_occur[pos-1] + leasts[pos-1];
                        }
                        last_occur[pos] = i;
                        
                        if (leasts.back() != -1 && pos == T.size()-1 && leasts.back() < min_len) {
                            min_len = leasts.back();
                            start_idx = i - min_len + 1;
                        }
                    }
                }
            }
    
            return (start_idx == -1) ? "" : S.substr(start_idx, min_len);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.