1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 25, 2014
4+ Problem: Minimum Window Substring
5+ Difficulty: Medium
6+ Source: https://oj.leetcode.com/problems/minimum-window-substring/
7+ Notes:
8+ Given a string S and a string T, find the minimum window in S which will contain all the
9+ characters in T in complexity O(n).
10+ For example,
11+ S = "ADOBECODEBANC"
12+ T = "ABC"
13+ Minimum window is "BANC".
14+ Note:
15+ If there is no such window in S that covers all characters in T, return the empty string "".
16+ If there are multiple such windows, you are guaranteed that there will always be only one unique
17+ minimum window in S.
18+
19+ Solution: 1. Use two pointers: start and end.
20+ First, move 'end'. After finding all the needed characters, move 'start'.
21+ 2. Use array as hashtable.
22+ */
23+
24+ public class Solution {
25+ public String minWindow (String S ,String T ) {
26+ int N =S .length (),M =T .length ();
27+ if (N <M )return new String ("" );
28+ int []need =new int [256 ];
29+ int []find =new int [256 ];
30+ for (int i =0 ;i <M ; ++i )
31+ need [T .charAt (i )]++;
32+
33+ int count =0 ,resStart = -1 ,resEnd =N ;
34+ for (int start =0 ,end =0 ;end <N ; ++end )
35+ {
36+ if (need [S .charAt (end )] ==0 )
37+ continue ;
38+ if (find [S .charAt (end )] <need [S .charAt (end )])
39+ count ++;
40+ find [S .charAt (end )]++;
41+ if (count !=M )continue ;
42+ // move 'start'
43+ for (;start <end ; ++start ) {
44+ if (need [S .charAt (start )] ==0 )continue ;
45+ if (find [S .charAt (start )] <=need [S .charAt (start )])break ;
46+ find [S .charAt (start )]--;
47+ }
48+ // update result
49+ if (end -start <resEnd -resStart ) {
50+ resStart =start ;
51+ resEnd =end ;
52+ }
53+ }
54+ return (resStart == -1 ) ?new String ("" ) :S .substring (resStart ,resEnd +1 );
55+ }
56+ }
