I thought my solution might be wrong, or at least TLE. I was a little surprised when it was accepted. I am thinking whether someone can design a case that makes this solution failed/TLE or give some complexity analysis.

The idea is very straightforward:

- search
`T`

starting at`S[p1]`

forwardly, and suppose it ends at`S[p2]`

; - search
`T`

starting at`S[p2]`

backwardly, and suppose it ends at`S[p3]`

; `S[p3:p2]`

is then a possible answer;- record the shortest answer and go to step 1 with
`p1 = p3 + 1`

.

Code:

```
class Solution {
public:
string minWindow(string S, string T) {
string out;
size_t p1 = 0;
while (p1 + T.size() < S.size()) {
size_t p2 = p1;
bool isEnd = false;
// forward search
for (size_t i = 0; i < T.size(); i++) {
while (S[p2] != T[i] && p2 < S.size()) {
p2++;
}
if (p2 == S.size()) {
isEnd = true;
break;
}
p2++;
}
if (isEnd)
break;
size_t p3 = --p2;
// backward search
for (int i = T.size() - 1; i >= 0; i--) {
while (S[p3] != T[i]) {
p3--;
}
p3--;
}
p3++;
// record the shortest answer
if (out.empty())
out = S.substr(p3, p2 - p3 + 1);
else
out = out.size() > (p2 - p3 + 1) ? S.substr(p3, p2 - p3 + 1) : out;
p1 = p3 + 1;
}
return out;
}
};
```