leetcode 727 - Minimum Window Subsequence

https://leetcode.com/problems/minimum-window-subsequence/

Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W.

If there is no such window in S that covers all characters in T, return the empty string “”. If there are multiple such minimum-length windows, return the one with the left-most starting index.

Example 1:

Input:
S = “abcdebdde”, T = “bde”
Output: “bcde”
Explanation:
“bcde” is the answer because it occurs before “bdde” which has the same length.
“deb” is not a smaller window because the elements of T in the window must occur in order.

Note:

All the strings in the input will only contain lowercase letters.
The length of S will be in the range [1, 20000].
The length of T will be in the range [1, 100].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
string minWindow(string S, string T) {
int size = S.size();
vector<vector<int>> next(size);
vector<int> pos(256, -1);

for (int i = size - 1; i >= 0; i--) {
next[i] = pos;
pos[S[i]] = i;
}

int p;
int min_len = INT_MAX;

for (int i = 0; i < size; i++) {
if (S[i] == T[0]) {
int j = i;
for (int k = 1; k < T.size() && j != -1; k++) {
j = next[j][T[k]];
}

if (j != -1 && j - i + 1 < min_len) {
p = i;
min_len = j - i + 1;
}
}
}

return min_len == INT_MAX ? "" : S.substr(p, min_len);
}
};