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

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

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