Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S =
T =
S =
"ADOBECODEBANC"
T =
"ABC"
Minimum window is
"BANC"
.
Note:
If there is no such window in S that covers all characters in T, return the empty string
If there is no such window in S that covers all characters in T, return the empty string
""
.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
Solution 1: Use a counter to store the count number of each character. C1 is for S and C2 is for T, use C1-C2 and maintain a slide window that count is non-negative.
public class Solution {
public String minWindow(String s, String t) {
int m=s.length();
int n=t.length();
if (m==0 || n==0) return "";
int[] c1=new int[256];
int[] c2=new int[256];
for (int i=0; i<m; i++) c1[s.charAt(i)]++;
for (int i=0; i<n; i++) c2[t.charAt(i)]++;
for (int i=0; i<256; i++) {
c1[i]-=c2[i];
if (c1[i]<0) return "";
}
int i=0, j=m-1, min=m;
String res=s;
while (c1[s.charAt(j)]>0) c1[s.charAt(j--)]--;
while (true) {
while (c1[s.charAt(i)]>0) c1[s.charAt(i++)]--;
if (j-i+1<min) {
min=j-i+1;
res=s.substring(i,j+1);
}
if (++j==m) break;
c1[s.charAt(j)]++;
}
return res;
}
}
没有评论:
发表评论