Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class Solution {
- public String minWindow(String S, String T) {
- if(T.isEmpty() || S.isEmpty()) {
- return "";
- }
- int tcount = 0;
- int minLen = Integer.MAX_VALUE;
- int[] needToFind = new int[128];
- int[] hasFound = new int[128];
- for(int i=0; i<T.length(); i++) {
- int c = T.charAt(i);
- needToFind[c]++;
- }
- int l = 0, r = 0;
- int minl = 0, minr = 0;
- for(; r<S.length(); r++) {
- int rc = S.charAt(r);
- if(needToFind[rc] > 0) {
- hasFound[rc]++;
- if(needToFind[rc] >= hasFound[rc]) {
- tcount++;
- }
- if(tcount == T.length()) {
- int lc = S.charAt(l);
- while(needToFind[lc] == 0 || needToFind[lc] < hasFound[lc]) {
- if(needToFind[lc] < hasFound[lc]) {
- hasFound[lc]--;
- }
- l++;
- lc = S.charAt(l);
- }
- if(r - l + 1 < minLen) {
- minr = r;
- minl = l;
- minLen = r - l + 1;
- }
- }
- }
- }
- if(tcount != T.length()) {
- return "";
- } else {
- return S.substring(minl, minr+1);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement