Skip to content

Instantly share code, notes, and snippets.

@wayetan
Created March 2, 2014 06:24
Show Gist options
  • Save wayetan/9302717 to your computer and use it in GitHub Desktop.
Save wayetan/9302717 to your computer and use it in GitHub Desktop.
Minimum Window Substring
/**
* 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 = "ADOBECODEBANC"
* T = "ABC"
* Minimum window is "BANC".
* Note:
* If there is no such window in S that covers all characters in T, return the emtpy string "".
* If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
*/
public class Solution {
public String minWindow(String S, String T) {
int sLen = S.length();
int tLen = T.length();
// initialize needToFind array
int[] needToFind = new int[256];
for(int i = 0; i < tLen; i++) {
needToFind[T.charAt(i)]++;
}
int[] hasFound = new int[256];
int minWinLen = Integer.MAX_VALUE;
int minWinBegin = 0;
int minWinEnd = 0;
int count = 0;
for(int begin = 0, end = 0; end < sLen; end++) {
// skip characters not in T
if(needToFind[S.charAt(end)] == 0)
continue;
hasFound[S.charAt(end)]++;
if(hasFound[S.charAt(end)] <= needToFind[S.charAt(end)])
count++;
// if window constraint is satisfied
if(count == tLen) {
// advance begin index as far as possible, stop when advancing breaks window constraint.
while(needToFind[S.charAt(begin)] == 0 || hasFound[S.charAt(begin)] > needToFind[S.charAt(begin)]) {
if(hasFound[S.charAt(begin)] > needToFind[S.charAt(begin)])
hasFound[S.charAt(begin)]--;
begin++;
}
// update minWindow if a minimum length is satisfied
int windowLen = end - begin + 1;
if(windowLen < minWinLen) {
minWinBegin = begin;
minWinEnd = end;
minWinLen = windowLen;
}
}
}
return (count == tLen) ? S.substring(minWinBegin, minWinEnd + 1) : "";
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment