# Minimum Window Subsequence

This page explains Java solution to problem `Minimum Window Subsequence` using `String` data structure.

## Problem Statement

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.

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
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;
}
}
``````

## Time Complexity

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

## Space Complexity

O(S) Where
S is total number of characters in an input string