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[0][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.