# C++ non-DP solution, O(MNln(M))

• Straight forward thought process:

1. Build map to store the position(s) each char of T have appeared at in S
2. Find the shortest increasing sequence S of positions in the map, such that S[0] is in map[T[0]], S[1] is in map[T[1]], ... S[N-1] is in map[T[N-1]], where N is T.size().

Not sure if I got the big O correct. Comments?

``````    string minWindow(string S, string T) {
unordered_map<int, vector<int>> locations;
unordered_set<char> myset;
for (auto c : T) {
myset.insert(c);
}
for (int i = 0; i < S.size(); i++) {
if (myset.count(S[i])) {
locations[S[i]].push_back(i);
}
}

int start = 0, len = INT_MAX;

for (int i = 0; i < locations[T[0]].size(); i++) {
size_t pos = locations[T[0]][i];
int iter = 1;
for (; iter < T.size(); iter++){
if (pos + 1 > locations[T[iter]].back())
break;
else{
pos = *lower_bound(locations[T[iter]].begin(), locations[T[iter]].end(), pos+1);
}
}
if (iter != T.size())
continue;
if (pos - locations[T[0]][i] + 1 < len) {
len = pos - locations[T[0]][i] + 1;
start = locations[T[0]][i];
}
}
if (len < INT_MAX)
return S.substr(start, len);
else
return "";
}
``````

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