Minimum Window Substring

string minWindow(string S, string T)
      {
          if (S.empty())return " ";
          if (S.size() < T.size())return " ";

          const int ASCII_MAX = 256;
          //定义数组，表示相应字符出现的次数
          int appeared_count[ASCII_MAX];
          int expected_count[ASCII_MAX];
          fill(appeared_count, appeared_count + ASCII_MAX, 0);
          fill(expected_count, expected_count + ASCII_MAX, 0);
          //统计目标串每个元素出现的次数
          for (int i = 0; i < T.size(); i++)expected_count[T[i]]++;
          
          int minWidth = INT_MAX, min_start = 0;//记录窗口大小，起点
          int wnd_start = 0;
          int appeared = 0;//

          //不断向后扫描
          for (int wnd_end = 0; wnd_end < S.size(); wnd_end++)
          {
              //如果当前元素在目标串中
              if (expected_count[S[wnd_end]]>0)
              {
                  //相应元素出现次数加1
                  appeared_count[S[wnd_end]]++;
                  //注意appeared自增的条件
                  if (appeared_count[S[wnd_end]] <= expected_count[S[wnd_end]])
                      appeared++;
              }

              if (appeared == T.size())//完整的包含了一个目标串
              {
                  //录找最小串，如果记录的某元素的数量大于目标某元素的数量，
                  //或者该元素在目标串中没有出现，则可以去掉一个
                  while (appeared_count[S[wnd_start]] > expected_count[S[wnd_start]] 
                      || expected_count[S[wnd_start]]==0)
                  {
                      appeared_count[S[wnd_start]]--;
                      wnd_start++;
                  }
                  //保留长度和起始位置
                  if (minWidth > wnd_end - wnd_start + 1)
                  {
                      minWidth = wnd_end - wnd_start + 1;
                      min_start = wnd_start;
                  }
              }

          }
          if (minWidth == INT_MAX)return " ";
          else return S.substr(min_start, minWidth);
      }