FilesExpand file tree

 master

/

MinimunWindowSubstring.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

47 lines (44 loc) · 1.13 KB

 master

/

MinimunWindowSubstring.java

Top

File metadata and controls

• Code
• Blame

47 lines (44 loc) · 1.13 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

public class Solution {

public String minWindow(String S, String T) {

// Start typing your Java solution below

// DO NOT write main() function

int[] needs = new int[256];

int[] has = new int[256];

//String re = "";

int shortest= S.length()+1;

int start=0;

int end=0;

int p=0;

int q=0;

int had = 0;

//get what we needs

for(int i=0; i<T.length(); i++){

needs[(int)T.charAt(i)]+=1;

}

while(q<S.length()){

char current = S.charAt(q);

has[(int)current]++;

if(has[(int)current]<=needs[(int)current]){

had++;

while(had == T.length()){

if(has[(int)S.charAt(p)]==needs[(int)S.charAt(p)]){

int templen = q-p+1;

if(shortest>templen){

shortest = templen;

start = p;

end = q;

}

had--;

}

has[(int)S.charAt(p)] --;

p++;

}

}

q++;

}

if(shortest < S.length()+1)

return S.substring(start,end+1);

else

return "";

}

}