题目描述

// 76. 最小覆盖子串

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

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

题解

// 维护数组hash，数组索引用于记录字母，数组元素用于记录t字符串指定字符的
// 出现次数和s字符串字符出现次数，ASCII表总长128，所以size是128。
// 记s长度为slen，t长度为tlen。s转为char[]记为schar，t转为char[]记为tchar，
// 维护数组hash，记录t字符串指定字符的出现次数和s字符串字符出现次数，
// ASCII表总长128所以size是128。
// 遍历tchar中所有字符，将hash位置中tchar的相应字符索引的对应元素累减1，
// 所以-1就是出现tchar的某字符1次，-2就是出现tchar的某字符2次。
// 
// 定义答案保存位res，初始化为""。
// for循环遍历schar字符，初始化schar右索引i和左索引j，初始化计数位count，
// 右索引i的遍历字符为schar[i]，则schar[i]在hash的相应位置累加1，用来记录
// schar字符的出现次数（hash[schar[i]]++）。
// 每次做条件判断，如果当前遍历右索引遍历字符schar[i]在字母记录表hash中小于等于0
// （hash[schar[i]] <= 0），说明当前右索引遍历字符schar[i]必为tchar中的字符，
// 匹配一个，count就累加计数一次。如此循环。
// 
// 直到count计数大小等于tlen，说明右索引i已在schar中遍历了所有与tchar字符相同
// 的字符，左索引j开始右移缩小窗口寻找子串。
// while循环，如果count等于tlen，且左索引j的
// 遍历字符schar[j]在hash字母记录表出现次数大于0，说明不是与tchar字符相同字符，
// 只被累加过，没有被累减过。则该字符需要舍弃在j 到 i的窗口外，
// 则该字符schar[j]在hash字母记录表的出现次数累减1，左索引j右移，
// 直到左索引遍历字符schar[j]在hash字母记录表出现次数小于等于0，说明找到了
// 从左到右第一个与tchar相同的字符。while循环停止，j停止右移。
// 
// 条件判断，如果count等于tlen，且如果res不为空，或res的长度大于
// j到i的窗口长度，由于题目需要最小子串，所以将res赋为s.substring(j, i + 1)
// 
// for循环结束后，返回res。

// 执行用时：4 ms, 在所有 Java 提交中击败了89.08%的用户
// 内存消耗：38.5 MB, 在所有 Java 提交中击败了90.72%的用户
class Solution {
    public String minWindow(String s, String t) {
		char[] schar = s.toCharArray();
		char[] tchar = t.toCharArray();
		int slen = s.length(), tlen = t.length();
		int[] hash = new int[128];
		for (char ch: tchar)
			hash[ch]--;
		String res = "";
		
		for (int i = 0, j = 0, count = 0; i < slen; i++) {
			hash[schar[i]]++;
			if (hash[schar[i]] <= 0) 
				count++;
			while (count == tlen && hash[schar[j]] > 0) {
				hash[schar[j]]--;
				j++;
			}
			if (count == tlen) {
				if (res.equals("") || res.length() > i - j + 1)
					res = s.substring(j, i + 1);
			}
		}
		return res;
    }
}