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".
[Analysis]
The problem can be resolved by using a window (tail, head) on string S.
1) Both indexes tail and head start from index 0 of S.
2) Move "head" forward step by step in S until find a window (tail, head) contain all the characters in T.
3) Then move "tail" forward to leave characters (in T) out of window, as many as possible until the sub-string in window cannot contain all characters in T.
4) Repeat 2, 3 until reach the end of S. Meanwhile, measure the length of window and record the minimum window as requested.
The time complexity is O(N).
The problem can be resolved by using a window (tail, head) on string S.
1) Both indexes tail and head start from index 0 of S.
2) Move "head" forward step by step in S until find a window (tail, head) contain all the characters in T.
3) Then move "tail" forward to leave characters (in T) out of window, as many as possible until the sub-string in window cannot contain all characters in T.
4) Repeat 2, 3 until reach the end of S. Meanwhile, measure the length of window and record the minimum window as requested.
The time complexity is O(N).
[Solution]
//
//--- C++ ---
//
class Solution {public:
string minWindow(string s, string t) {
unordered_map<char, int> target;
for (auto c: t)
target[c]++;
unordered_map<char, int> counter;
auto contained=[&]() {
for (auto& t: target)
if (t.second>counter[t.first]) return false;
return true;
};
int i=0, j=0;
int ri=0, rj=INT_MAX;
while (j<s.size()) {
while (!contained() && j<s.size())
counter[s[j++]]++;
while(contained() && i<j) {
if (j-i<rj-ri)
ri=i, rj=j;
counter[s[i++]]--;
}
}
return rj-ri<=s.size()?s.substr(ri, rj-ri):"";
}
};
//
//--- Java ---
//
public String minWindow(String S, String T) {
if (S.length() < T.length() || T.length()==0) return "";
String minStr = S+" ";
S.toUpperCase();
T.toUpperCase();
// -- cnt arrays used for judging whether all characters
// in target string are included in window sub-string.
int[] wndCnts = new int[26];
int[] tgtCnts = new int[26];
char[] temp = T.toCharArray();
for (char c: temp) {
tgtCnts[c-'A'] ++;
}
int loadFlag = setFlag(T);
int loadFlagCopy = loadFlag;
int head, tail;
head = tail =0;
// -- skip letters that not meaningful --
while (!charInTarget(S.charAt(head), tgtCnts)) {
head++;
};
tail = head;
// -- start looping --
while (head < S.length() ) {
while (!charInTarget(S.charAt(tail), tgtCnts)) {
tail++;
};
// -- grow to the match --
while (head < S.length() && loadFlag!=0) {
char c= S.charAt(head++);
if (charInTarget(c, tgtCnts)) {
wndCnts[c-'A']++;
if (wndCnts[c-'A']==tgtCnts[c-'A']) {
loadFlag ^= 1<<(c-'A');
}
}
}
if (loadFlag == 0) {
if (minStr.length()>head-tail) {
minStr = S.substring(tail, head);
}
}
else break;
// -- reduce the match --
int unloadFlag = 0;
while(tail<head && unloadFlag==0) {
char c= S.charAt(tail++);
if (charInTarget(c, tgtCnts)) {
wndCnts[c-'A']--;
if (wndCnts[c-'A']<tgtCnts[c-'A']) {
unloadFlag = 1<<(c-'A');
}
else if (minStr.length()>head-tail) {
minStr = S.substring(tail, head);
}
}
}
loadFlag = loadFlagCopy & unloadFlag;
}
if (minStr.equals(S+" ")) return "";
return minStr;
}
int setFlag (String s) {
char[] chars = s.toCharArray();
int a = 0;
for (char c: chars) {
a |= 1<<(c-'A');
}
return a;
}
boolean charInTarget (char c, int[] target) {
return (target[c-'A']>0);
}
public void runTestCases() {
String[] S = {"ADOBECODEBANC", "ABBADBABDRGBACCCB", "HBBHHCADBEBCAECBCCBB"};
String[] T = {"ABC", "ABBC", "ABBC"};
for (int i=0; i<S.length; i++) {
String ret = minWindow(S[i], T[i]);
System.out.println(ret);
}
}
}
Dude, have you tested online by leetcode? I had the essentially same logic but couldn't pass large data set.
ReplyDeleteHi, Jason, I did not use leetcode to test this. I used my own data and test program.
ReplyDelete