FilesExpand file tree

 master

/

MinWindowSubString.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

73 lines (57 loc) · 2.21 KB

 master

/

MinWindowSubString.java

Copy path

Top

File metadata and controls

• Code
• Blame

73 lines (57 loc) · 2.21 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

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

/**

* 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".

*/

public class MinWindowSubString {

public static void main(String[] args) {

String[] S = {"ADOBECODEBANC", "ABBADBABDRGBACCCB", "HBBHHCADBEBCAECBCCBB"};

String[] T = {"ABC", "ABBC", "ABBC"};

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

String ret = minWindowSubString(S[i], T[i]);

System.out.println(ret);

}

}

public static String minWindowSubString(String source, String test) {

source.toUpperCase();

test.toUpperCase();

char[] sourceArray = source.toCharArray();

char[] testArray = test.toCharArray();

int sLen = source.length();

int tLen = test.length();

int minWindow = Integer.MAX_VALUE;

int minEnd = 0, minStart = 0;

int start = 0, end = 0, foundCounter = 0;

int[] needToFind = new int[256];

int[] hasFound = new int[256];

for (int i = 0; i < tLen; ++i)

needToFind[testArray[i]]++;

for (; end < sLen; end++) {

char endChar = sourceArray[end];

if (needToFind[endChar] == 0)

continue;

hasFound[endChar]++;

if (hasFound[endChar] <= needToFind[endChar])

foundCounter++;

if (foundCounter == tLen) { // found all

char startChar = sourceArray[start];

while (needToFind[startChar] == 0

|| hasFound[startChar] > needToFind[startChar]) {

if (hasFound[startChar] > needToFind[startChar])

hasFound[startChar]--;

start++;

startChar = sourceArray[start];

}

int currentWindow = end - start + 1;

if (currentWindow < minWindow) {

minWindow = currentWindow;

minEnd = end;

minStart = start;

}

}

}

return (foundCounter == tLen) ? source.substring(minStart, minEnd + 1) : "";

}

}