# C++, AC, 16ms, O(1) space, not DP

• 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:

1. search `T` starting at `S[p1]` forwardly, and suppose it ends at `S[p2]`;
2. search `T` starting at `S[p2]` backwardly, and suppose it ends at `S[p3]`;
3. `S[p3:p2]` is then a possible answer;
4. 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++;
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;
}
};
``````

• I have the same thought and I was confused by how to measure the time complexity of this algorithm. However, I don't think the answer is incorrect.

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