This page explains Java solution to problem `Minimum Window Subsequence`

using `String`

data structure.

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.

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.

```
package com.vc.hard;
class MinimumWindowSubsequence {
public String minWindow(String s, String t) {
if(s == null || s.length() == 0 || t == null || t.length() == 0) return "";
String ans = "";
int ti = 0, si = 0, end = 0;
while(si < s.length()) {
if(s.charAt(si) == t.charAt(ti)) {
ti++;
if(ti == t.length()) {
ti--;
end = si + 1;
while(ti >= 0) {
if(t.charAt(ti) == s.charAt(si)) ti--;
si--;
}
ti++;
si++;
if(ans.equals("") || ans.length() > end - si) {
ans = s.substring(si, end);
}
}
}
si++;
}
return ans;
}
}
```

O(S + (S / T)) Where

S is total number of characters in an input string

T is total number of characters in an input subsequence

O(S) Where

S is total number of characters in an input string