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