[PHP知识库]最小覆盖子串【php版】

	/**
	 * 使用滑动窗口标准模板解决即可
	 * @param String $s
	 * @param String $t
	 * @return String
	 */
	function minWindow($s, $t) {
		// 先统计目标字串中各字符的出现次数
		$_tCount = array_count_values(str_split($t));
		// $t 中不同字符的个数
		$_tN = count($_tCount);

		$_sLen = strlen($s);
		// 用于记录在滑动窗口中的字符出现次数
		$_winCount = [];
		// 用于记录既在winCount,又在tCount中,且在winCount中记录的出现次数 >= tcount中的字符数目
		// 说白了，只有 valid == tN 滑动窗口中的字符才符合题目的要求
		$valid = 0;
		// 用于记录结果窗口的左端点
		$ansL = 0;
		// 用于记录窗口的左端点
		$l = 0;
		// 用于记录窗口的右端点
		$r = 0;
		// 用于记录滑动窗口的最小长度
		$ansMinLen = PHP_INT_MAX;
		while ($r<$_sLen) {
			$char = $s[$r];
			if (array_key_exists($char, $_tCount)) {
				$_winCount[$char] = isset($_winCount[$char]) ? ++$_winCount[$char] : 1;
				if ($_winCount[$char] == $_tCount[$char]) {
					$valid++;
				}
			}
			// 当窗口中元素符合要求时，尝试缩小窗口
			while ($valid == $_tN && $l <= $r) {
				if ($r-$l+1 < $ansMinLen) {
					$ansMinLen = $r-$l+1;
					$ansL = $l;
				}
				if (array_key_exists($s[$l], $_winCount)) {
					$_winCount[$s[$l]]--;
					if ($_winCount[$s[$l]] < $_tCount[$s[$l]]) {
						// 如果退出窗口的元素导致当前滑动窗口的元素不满足要求了，将valid减少，以跳出循环
						$valid--;
					}
				}
				$l++;
			}
			// 扩张窗口
			$r++;
		}
		return $ansMinLen == PHP_INT_MAX ? '' : substr($s, $ansL, $ansMinLen);
	}