P103 包含给定字符的最短子串

描述#

这个题目说的是，给你两个字符串 s 和 t，你要在 s 中找到一个最短子串，它包含 t 中所有的字符。如果找不到满足条件的子串，就返回空字符串。

比如说，给你的字符串 s 和 t 分别是：
s: adbcacab
t: aab
在字符串 s 中，包含 a,a,b 这三个字符的最短子串是 acab，于是你要返回它。

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(m)
  public String minSubstringContainT(String s, String t) {
    if (s == null || t == null) return "";
    int[] required = new int[256];
    int start = 0, len = Integer.MAX_VALUE, requiredCnt = t.length();
    int left = 0, right = 0;
    for (int i = 0; i < t.length(); ++i) {
      ++required[t.charAt(i)];
    }

    for (; right < s.length(); ++right) {
      char r = s.charAt(right);
      if (required[r] > 0) --requiredCnt;
      --required[r];

      while (requiredCnt == 0) {
        if (right-left+1 < len) {
          start = left;
          len = right - left + 1;
        }
        char l = s.charAt(left);
        ++required[l];
        if (required[l] > 0) ++requiredCnt;
        ++left;
      }
    }
    return len == Integer.MAX_VALUE ? "" : s.substring(start, start+len);
  }

}