使用滑动窗口思想查找包含字符的最小覆盖子串

给定一个字符串S和字符串T，要求找出S中包含T中所有字符的最小子串，不需要满足顺序，要求时间复杂度O(n)

如：

例子1：

String S ="XDOYEZODEYXNZ";

String T ="XYZ" ;

返回 YXNZ

String S ="abcAbA";

String T ="AA" ;

返回 AbA

传统的方法是使用暴力解法，写两个双层循环，但是这样话，时间复杂度为 O(n2)，n的平方了，而不是O(n)了

所以使用双层循环肯定是不行了，这里只能使用滑动窗口的思想来解决

滑动窗口的思想大概如下：

假设定义滑动窗口的左端为left、右端为right

1 先固定left，right=left，right右移动，并判断字符是否包含在T中，包含则计数

2 当left和right之间刚好满足包含T的所有字符时，找到了子串[left,right]，但这个子串还不是最短的；

3 接下来就是缩短子串[left,right]，改变left、right使当前子串缩短

因为是刚好找到满足的条件，所以S[right]必定包含在T中，所以右端不能再变，也就是right不能变了，

只能移动left，由以下2种情况left是可以右移动的：

1）如果left对应的字符不包含在T中，说明该字符可以舍弃

2）如果left对应的字符包含在T中，但是该字符串在子串中个数已经大于T中对应的字符的个数了，表明也可以舍弃，

比如子串中a有3个，T中a2个，那么子串中减少一个a后，仍然满足包含T的所有字符，所以这种情况也可以舍弃字符

使用while循环移动left，直到left对应的字符不满足1）和2）为止，则此时是left和right就是当前的最小子串

4 比较当前的最小子串宽度是否大于前面找到的最小子串，如果大于，则使用第3步中的结果，否则舍弃第3步的结果

5 left右移一位，同时计数条件减1，重复 1、2、3、4的过程

因为此时的left的字符必定包含在T中，移动则当前子串丢失该字符串，会导致包含条件不满足了，所以计数条件要减一

单看我的描述可能理解会比较吃力，还是要看代码吧，里面也有对应的注释

代码如下：

import java.util.HashMap;
import java.util.Map;
/**
 * 使用滑动窗口思想
 * 在S串中寻找包含字符串T的所有字符的最小子串
 * 
 * 例如：
    S ="XDOYEZODEYXNZ"
    T ="XYZ"T="XYZ"
        找 出的最短子串为"YXNZ"
 * @author ssj
 *
 */
public class MinStringWindow {
	public static void main(String[] args) {
		String S ="XDOYEZODEYXNZ";
		String T ="XYZ" ;
		
//		String S ="abcAbA";
//		String T ="AA" ;
		
		
		String min = minWindow(S,T);
		System.out.println(min);
	}
	/**
	 * 在S字符串中查找包含T所有字符的最小子串
	 * @param S 原串
	 * @param T 目标串
	 * @return
	 */
	public static String minWindow(String S, String T) {
		
		if(S==null||T==null||S.length()<T.length()) {
			return null;
		}
		if(T.equals("")) {
			return T;
		}
		int minStart=0;//目标返回的滑动窗口的左端位置
		int width=Integer.MAX_VALUE;//目标返回的滑动窗口的宽度，初始化为最大
		int left=0;//滑动窗口的左边位置
		int right=0;//滑动窗口的右边位置
		int count=0;//监视需要包含的字符已经满足的个数，相同字符超过T中对应字符时不加1
		Map<Character, Integer> window = new HashMap<>();//统计T中的每个字符的个数
		Map<Character, Integer> need = new HashMap<>();//S的子串中获取到的T中的字符个数，用于动态记录
        int i=0;
        //统计T中每个字符的个数，放入map window中
        while(i<T.length()) {
        	window.put(T.charAt(i), window.getOrDefault(T.charAt(i), 0)+1);
        	i++;
        }
        
        while(right<S.length()) {
        	char c = S.charAt(right);
        	if(window.get(c)!=null) {
        		need.put(c, need.getOrDefault(c, 0)+1);
        		if(need.getOrDefault(c, 0)<=window.get(c)) {
        			//字符个数还没达到要求的个数，count计数，超过要求的个数不用计数
        			count++;
        		}
        		//当前子串已经找到包含T的所有字符
        		if(count==T.length()) {
        			//一旦找到了包含T的所有的字符的子串,缩短滑动窗口的宽度，子串左边向右移动，减少无效的字符
        			c=S.charAt(left);
        			//如果该字符需要在T中出现，并且need中的个数大于window中个数，表明可以舍弃该字符，该子串仍然包含T的所有字符
        			//如果该字符不包含在T中，那么这个字符是多余的，可以舍弃
        			while(need.getOrDefault(c, 0)>window.getOrDefault(c, 0)||window.get(c)==null&&left<=right) {
        				//如果该在包含在T中，子串舍弃了该字符，当然need中对应该字符的个数也要减一
        				if(need.get(c)!=null) {
        					need.put(c, need.getOrDefault(c, 0)-1);
        				}
        				left++;
        				c=S.charAt(left);
        			}
        			//判断本次的子串是否比上一次的子串长度小，小则，更新滑动窗口的宽度和起始索引
        			if(width>right-left+1&&left<=right) {
        				width=right-left+1;
        				minStart=left;
        			}
        			//找下一个满足的滑动窗口区间，left前进一位
        			if(left<S.length()) {
        				if(need.getOrDefault(c, 0)>0&&need.getOrDefault(c, 0)<=window.getOrDefault(c, 0)) {
        					//跳过的是包含的字符，此时减少一个字符，条件就不满足了，所以count要减一
        					need.put(c, need.getOrDefault(c, 0)-1);
        					count--;
        				}
        				left++;
        			}
        		}
        		
        	}
        	
        	right++;
        	
        }
        
		
        return width==Integer.MAX_VALUE?null:S.substring(minStart, minStart+width);
    }
}

运行结果：

YXNZ