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.

At first, I was thinking, I can just use an array and store every substring of S that starts and ends with a character in T and contains the rest of characters in T, and calculate the minimum substring of all. Apparently it cannot pass the Time Limit! Well, it's O(n^2) complexity, which probably a little bit too slow.

I searched online, and found this one. The idea is similar, search all the substrings that contains all the characters in T. However, this method uses two hash map, one to store the characters in T and the other one store the characters that are also in T in substrings of s. Meanwhile, we count those characters stored in the second hash map, when it equals the length of T, we move the left bound to get the substring.

In order for the substring to have minimum length, the substring must starts and ends with a character in T and ideally contains no more than one character of each character in T.

public class MinWindow {
    public String minWindow(String S, String T) {
        if (S == null || S.length() == 0)
   return S;
  if (T == null || T.length() == 0)
   return "";
  HashMap tCh = new HashMap();
  for (int i = 0; i < T.length(); i++)
  {
      if (!tCh.containsKey(T.charAt(i)))
          tCh.put(T.charAt(i), 1);
      else
          tCh.put(T.charAt(i), tCh.get(T.charAt(i)) + 1);
  }
  
  HashMap window = new HashMap();
  int leftBound = 0;
  int tCount = 0;
  String minWindow = null;
  for (int i = 0; i < S.length(); i++)
  {
      char ch = S.charAt(i);
      if (!tCh.containsKey(ch))
          continue;
      if (!window.containsKey(ch))
          window.put(ch, 1);
      else
          window.put(ch, window.get(ch) + 1);
      if (window.get(ch) <= tCh.get(ch))
          tCount++;
      if (tCount == T.length())
      {
          while(leftBound < S.length())
          {
              if(!window.containsKey(S.charAt(leftBound)))
              {
                  leftBound++;
                  continue;
              }
              if(window.get(S.charAt(leftBound)) > tCh.get(S.charAt(leftBound)))
              {
                  window.put(S.charAt(leftBound), window.get(S.charAt(leftBound)) - 1);
                  leftBound++;
                  continue;
              }
               break;   
              
          }
          if (minWindow == null || minWindow.length() > (i - leftBound + 1))
          {
              minWindow = S.substring(leftBound, i + 1);
          }
          
      }
  }
  if(minWindow == null)
      return "";
  return minWindow;
    }
        
}

Couldn't help to post my failed solution here, maybe if I trim a little bit, it may pass.

public class MinWindowSubstring {
 public String minWindow(String S, String T)
 {
  if (S == null || S.length() == 0)
   return S;
  if (T == null || T.length() == 0)
   return "";
  int leftBound = 0;
  ArrayList rsts = new ArrayList();
  int tLength = T.length();
  while (leftBound <= S.length() - tLength)
  {
   while (leftBound < S.length() && !T.contains(String.valueOf(S.charAt(leftBound))))
   {
    leftBound++;
   }
   
   int rightBound = leftBound + tLength;
   if (rightBound > S.length())
    break;
   String tmp = S.substring(leftBound, rightBound);
   while (rightBound < S.length() && !containsString(tmp, T))
   {
    rightBound++;
    if (S.charAt(leftBound) == S.charAt(rightBound - 1))
    {
     leftBound++;
     while (!T.contains(String.valueOf(S.charAt(leftBound))))
      leftBound++;
    }
     
    tmp = S.substring(leftBound, rightBound);
   }
   if (containsString(tmp, T))
    rsts.add(tmp);
   leftBound++;
  }
  if (rsts.size () == 0)
   return "";
  String rst = rsts.get(0);
  int minLength = rsts.get(0).length();
  System.out.println(rsts.get(0));
  for (int i = 1; i < rsts.size(); i++)
  {
   System.out.println(rsts.get(i));
   if (rsts.get(i).length() < minLength)
   {
    rst = rsts.get(i);
    minLength = rsts.get(i).length();
   }
  }
  return rst;
   
  
 }
 private boolean containsString (String S, String T)
 {
  for (int i = 0; i < T.length(); i++)
  {
   if (!S.contains(String.valueOf(T.charAt(i))))
    return false;
  }
  return true;
        }
}