76. 最小覆盖子串-蒲公英云

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

示例 2：

输入：s = "a", t = "a"
输出："a"

提示：

1 <= s.length, t.length <= 105
s 和 t 由英文字母组成

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

package Solution76;
class Solutiontimeout {
    public String minWindow(String s, String t) {
        int tlen=t.length();
        int start = 0;
        int end = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + tlen; j <= s.length(); j++) {
                // System.out.println(s.substring(i, j));
                if (contain(s.substring(i, j), t)) {
                    if ((j - i) < min) {
                        min = j - i;
                        start = i;
                        end = j;
                    }
                }
            }
        }
        return s.substring(start, end);
    }
    public boolean contain(String s, String t) {
        for (int i = 0; i < t.length(); i++) {
            String temp = s.replaceFirst(t.substring(i, i + 1), "");
            if (temp.length() != s.length() - 1) {
                return false;
            }
            s = temp;
        }
        return true;
    }
    public static void main(String[] args) {
        Solutiontimeout sol = new Solutiontimeout();
        String s = "ADOBECODEBANC", t = "ABC";
        System.out.println(sol.minWindow(s, t));
    }
}