## 727. 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]`.

## Rust Solution

``````struct Solution;

impl Solution {
fn min_window(s: String, t: String) -> String {
let m = t.len();
let n = s.len();
let s: Vec<char> = s.chars().collect();
let t: Vec<char> = t.chars().collect();
let mut dp: Vec<Vec<usize>> = vec![vec![0; n + 1]; m + 1];
for j in 0..=n {
dp[j] = j + 1;
}
for i in 1..=m {
for j in 1..=n {
if t[i - 1] == s[j - 1] {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
let mut start = 0;
let mut len = std::usize::MAX;
for j in 1..=n {
if dp[m][j] != 0 {
if j - dp[m][j] + 1 < len {
start = dp[m][j] - 1;
len = j - dp[m][j] + 1;
}
}
}
if len == std::usize::MAX {
"".to_string()
} else {
s[start..start + len].iter().collect()
}
}
}

#[test]
fn test() {
// let s = "abcdebdde".to_string();
// let t = "bde".to_string();
// let res = "bcde".to_string();
// assert_eq!(Solution::min_window(s, t), res);
let s = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl".to_string();
let t = "l".to_string();
let res = "l".to_string();
assert_eq!(Solution::min_window(s, t), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.