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.

不会做，看了别人的程序，自己按他的思路写了个。当作学学别人的编程技巧了。

class Solution { public: string minWindow(string s, string t) { int slength=s.size(); int tlength=t.size(); int alphArray[128]; fill_n(alphArray,128,-slength); int minS,minL=INT_MAX; for(int i=0;i<tlength;++i) alphArray[t[i]]=alphArray[t[i]]>0?(++alphArray[t[i]]):1; int start=0; for(int i=0,count=tlength;i<slength;++i) { if((--alphArray[s[i]]>=0) && (--count==0)) { while(alphArray[s[start]]<=-slength || (++alphArray[s[start]]<=0)) ++start; if(minL>i-start+1) { minL=i-start+1; minS=start; } count=1;//因为丢弃了一个 ++start; } } return minL==INT_MAX?"":s.substr(minS,minL); } };

以上程序中包括了两个头文件：<limits.h>、<algorithm>;前者定义了部分数据类型的极限取值（INT_MAX），，后者是STL中相关算法（fill_n）

limits.h头文件内容如下：

C语言的数据类型有四种：整形、浮点型、指针、聚合类型（数组、结构等），其中整形家族的变量包括：char, int, short, long, enum等。浮点数家族包括float, double等。

limits.h头文件对整形家族变量范围进行了宏定义。float.h定义了FLT_MAX, FLT_MIN, DBL_MAX, DBL_MIN。下面这张表搬运自维基百科。

Name Description Typical value ANSI standard minimum-
or maximum magnitude value
CHAR_BIT   Number of bits in a char   8   ≥+8  
SCHAR_MIN   Minimum value for a signed char   –128   ≤–127  
SCHAR_MAX   Maximum value for a signed char   +127   ≥+127  
UCHAR_MAX   Maximum value for an unsigned char   +255   ≥+255  
CHAR_MIN   Minimum value for a char   –128   ≤–127
(if char is represented as a
signed char; otherwise ≤0)  
CHAR_MAX   Maximum value for a char   +127   ≥+127
(if char is represented as a
signed char; otherwise ≥+255)  
MB_LEN_MAX   Maximum multi byte length of a character across all locales   varies, usually at least 4   ≥+1  
SHRT_MIN   Minimum value for a short int   –32,768   ≤–32,767  
SHRT_MAX   Maximum value for a short int   +32,767   ≥+32,767  
USHRT_MAX   Maximum value for an unsigned short int   +65,535   ≥+65,535  
INT_MIN   Minimum value for an int   –2,147,483,648   ≤–32,767  
INT_MAX   Maximum value for an int   +2,147,483,647   ≥+32,767  
UINT_MAX   Maximum value for an unsigned int   +4,294,967,295   ≥+65,535  
LONG_MIN   Minimum value for a long int   32 bit compiler   –2,147,483,648   ≤–2,147,483,647  
64 bit compiler   –9,223,372,036,854,775,808  
LONG_MAX   Maximum value for a long int   32 bit compiler   +2,147,483,647   ≥+2,147,483,647  
64 bit compiler   +9,223,372,036,854,775,807  
ULONG_MAX   Maximum value for an unsigned long int   32 bit compiler   +4,294,967,295   ≥+4,294,967,295  
64 bit compiler   +18,446,744,073,709,551,615  
LLONG_MIN   Minimum value for a long long int   –9,223,372,036,854,775,808   ≤-9,223,372,036,854,775,807  
LLONG_MAX   Maximum value for a long long int   +9,223,372,036,854,775,807   ≥+9,223,372,036,854,775,807  
ULLONG_MAX   Maximum value for an unsigned long long int   +18,446,744,073,709,551,615   ≥+18,446,744,073,709,551,615
 

leetCode(55):Minimum Window Substring（limits.h头文件）