MinimumWindowSubstring

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class MinimumWindowSubstring {
  public static void main(String []argv) {
		MinimumWindowSubstring mws = new MinimumWindowSubstring();

		System.out.println(mws.minWindow("ADOBECODEBANC", "ABC"));
		System.out.println(mws.minWindow("aa", "aa"));
	}

  public String minWindow(String S, String T) {
    // won't have valid answer
    if (S.length() < T.length() || S.equals("")) {
      return "";
    }

    HashSet<Character> careSet = new HashSet<Character>();  // set of characters we care about
    HashMap<Character, Integer> remain = new HashMap<Character, Integer>(); // character histogram
    HashMap<Character, Integer> spare = new HashMap<Character, Integer>();

    for (int i = 0; i < T.length(); i++) {
      char c = T.charAt(i);
      careSet.add(c);
      increase(c, remain);
    }

    int start = 0;
    int end = 0;
    int minLen = Integer.MAX_VALUE;
    int minStart = 0;
    int minEnd = 0;

    while (end < S.length() || (remain.isEmpty() && start < S.length())) {
      if (!remain.isEmpty()) {
        // expand end index
        char c = S.charAt(end);
        if (careSet.contains(c)) {
          if (remain.containsKey(c)) {
            decrease(c, remain);
          } else {
            increase(c, spare);
          }
        }
        end++;
      } else {
        // shrink start index
        // save shortest
        if (end - start < minLen) {
          minLen = end - start;
          minStart = start;
          minEnd = end;
        }
        char c = S.charAt(start);
        if (careSet.contains(c)) {
          if (spare.containsKey(c)) {
            decrease(c, spare);
          } else {
            increase(c, remain);
          }
        }
        start++;
      }
    }
    return (minLen != Integer.MAX_VALUE) ? S.substring(minStart, minEnd) : "";
  }

  private void decrease(char c, Map<Character, Integer> map) {
    if (map.containsKey(c)) {
      if (map.get(c) == 1) {
        map.remove(c);
      } else {
        map.put(c, map.get(c) - 1);
      }
    }
  }

  private void increase(char c, Map<Character, Integer> map) {
    if (map.containsKey(c)) {
      map.put(c, map.get(c) + 1);
    } else {
      map.put(c, 1);
    }
  }
}