Leetcode Minimum Window Substring

Minimum Window Substring
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.
これはまた複雑な問題で、処理しなければならないことが多く、うっかりすると間違いを犯すことがあります.
本題の考え方:
2つのテーブルを使用して、アルファベットを下付きにして、1つのレコードアルファベットが現れる総回数、1つのレコード現在の検索でアルファベットが現れる回数を記録します.
処理状況:
1重複するサブ文字の場合、中間の重複文字は特殊な処理を必要とせず、最左の重複文字を処理するだけで、最左の指標は右に進みます.
2現在何個の合法的なサブ文字が現れているかを記録し、何度も繰り返して現れた非合法的な文字を計算し、合法的な文字がサブ文字の長さに等しい場合は、ウィンドウが見つかります.
状況に応じて処理するのは難しいが、どうやってこのタイプの問題に淡々と対処できるのか、まだ楽な方法が見つかっていない.

string minWindow(string S, string T) 
	{
		int fixedTable[256] = {0};
		int countingTable[256] = {0};

		int tn = T.length();
		for (int i = 0; i < tn; i++)
		{
			fixedTable[T[i]]++;
		}

		int minLen = INT_MAX, len = 0;
		int Tcount = 0;
		int sn = S.length();
		string rs("");

		//           
		int start = 0;
		while (start < sn && fixedTable[S[start]] == 0) start++;

		for (int i = start; i < sn; i++)
		{
			len++;
			//            
			if (fixedTable[S[i]] != 0)
			{
				//    ++
				countingTable[S[i]]++;
				//              ：
				if (countingTable[S[i]] <= fixedTable[S[i]])
				{
					Tcount++;
				}
				//      ，Tcount              
				//       ：
				if (Tcount == tn)
				{
					if (len < minLen)
					{
						minLen = len;
						//substr  ，      
						rs = S.substr(i-len+1, len);
					}

					//         
					countingTable[S[i-len+1]]--;
					len--;
					Tcount--;
					//lend==0             ，   T.length()==1   。
					while (len>0 && fixedTable[S[i-len+1]] == 0)
					{
						len--;
					}
				}

				//                   
				while (countingTable[S[i-len+1]] > fixedTable[S[i-len+1]])
				{
					//         
					countingTable[S[i-len+1]]--;
					//Tcount--;            Tcount ，  --
					len--;

					// T    
					while (fixedTable[S[i-len+1]] == 0)
					{
						len--;
					}
				}
			}//if (fixedTable[S[i]] != 0)
		}

		return rs;
	}

次は私が最初に書いたプログラムで、このプログラムは中間に重複文字が含まれないと仮定したので、通過しませんでした.
しかし、テーマを変更すると、このプログラムが使えるので、保留します.

//          
	string minWindow2(string S, string T) 
	{
		int fixedTable[256] = {0};
		int countingTable[256] = {0};

		int tn = T.length();
		for (int i = 0; i < tn; i++)
		{
			fixedTable[T[i]]++;
		}

		int minLen = INT_MAX, len = 0;
		int Tcount = 0;
		int sn = S.length();
		string rs("");

		//           
		int start = 0;
		while (start < sn && fixedTable[S[start]] == 0) start++;

		for (int i = start; i < sn; i++)
		{
			len++;
			//            
			if (fixedTable[S[i]] != 0)
			{
				//    ++
				countingTable[S[i]]++;
				Tcount++;
				//      table  ，         
				if (countingTable[S[i]] <= fixedTable[S[i]])
				{
					//      ，Tcount              
					if (Tcount == tn)
					{
						if (len < minLen)
						{
							minLen = len;
							//substr  ，      
							rs = S.substr(i-len+1, len);
						}

						//         
						countingTable[S[i-len+1]]--;
						len--;
						Tcount--;
		//lend==0             ，   T.length()==1   。
						while (len>0 && fixedTable[S[i-len+1]] == 0)
						{
							len--;
						}
					}
				}
				//          
				else
				{
					while (S[i-len+1] != S[i])
					{
						if (fixedTable[S[i-len+1]])
						{
							//  ：     countingTalbe
							countingTable[S[i-len+1]]--;
							Tcount--;
						}
						len--;
					}
					//      :len, Tcount countingTable       
					countingTable[S[i]]--;
					//         ，        len Tcount
					len--;
					Tcount--;

					while (fixedTable[S[i-len+1]] == 0)
					{
						len--;
					}
				}
			}//if (fixedTable[S[i]] != 0)
		}

		return rs;
	}

//2014-2-11 update
	string minWindow(string S, string T) 
	{
		int A[256] = {0};
		int B[256] = {0};
		for (int i = 0; i < T.length(); i++) A[T[i]]++;//T[i] or T[i]-'a'
		int c = 0;
		int begin = 0, len = INT_MAX;

		int i = 0;
		while (i < S.length() && !A[S[i]]) i++;

		for (int j = i; j < S.length(); j++)
		{
			if (A[S[j]])
			{
				B[S[j]]++;
				if (B[S[j]] <= A[S[j]])
				{
					if (++c == T.length())//founded
					{
						if (len > j-i+1)//save result
						{
							begin = i; 
							len = j-i+1;
						}
						--c; --B[S[i]]; 
						for (++i; i<j && (!A[S[i]] || A[S[i]] < B[S[i]]); ++i)
							if (A[S[i]]) B[S[i]]--;//i<j    
					}
				}
				else if (S[j] == S[i])//handle repeated
				{
					B[S[i]]--;
					for (++i; i<j && (!A[S[i]] || A[S[i]] < B[S[i]]); ++i)
						if (A[S[i]]) B[S[i]]--;
				}
			}//if (A[idx])...
		}//for (int j = i;...
		return INT_MAX == len? "":S.substr(begin, len);// T.length() > S.length()
	}