（细节题）[LeetCode]Minimum Window Substring

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

Question
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

本题难度Hard。

双指针法

【复杂度】
时间 O(N) 空间 O(1)

【思路】
用一个数组记录目标字符串每个字母的个数，一个数组记录窗口中每个字母的个数（字符的ascii码就是数组下标）。当找到有效的窗口后（满足条件found==t.length()），再将左边界尽量的右缩，右缩的条件是窗口中字母的个数不小于目标字符串中字母的个数，目的是清除无效字符，比如：

s= e f a a b b c d
t= a b c
对于第一个有效窗口为：
  start 
   |
s= e f a a b b c d
               |
               i
这时要让start越过 e、f 和 第一个a
       start 
         |
s= e f a a b b c d
               |
               i

然后与minLen判断是否为更小值，如果是则刷新最小窗口的minLen以及其边界begin和end。然后还要让start向右移动一次以便找下一个有效窗口，这步不是多余的，对于：

s= a b b b c b a
t= a b c
第一个有效窗口：
  start 
   |
s= a b b b c b a
           |
           i
如果不移动start，是不可能找到真正的最小string：
          start 
           |
s= a b b b c b a
               |
               i

【附】

[Leetcode] Minimum Window Substring 最小字符串窗口中对于本文代码第19行的条件是：start < i && destHash[S.charAt(start)] > srcHash[S.charAt(start)]，实际上并不需要start < i，因为start不可能能大于i。

【代码】

public class Solution {
    public String minWindow(String s, String t) {
        //require
        int[] srcHash=new int[255],desHash=new int[255];
        for(int i=0;i<t.length();i++)
            srcHash[t.charAt(i)]++;
        int begin=-1,end=s.length(),minLen=s.length(),found=0;
        int start=0;
        //invariant
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            // 每来一个字符给它的出现次数加1
            desHash[c]++;
            // 如果加1后这个字符的数量不超过目标串中该字符的数量，则找到了一个匹配字符
            if(desHash[c]<=srcHash[c])found++;
            //找到了有效窗口
            if(found==t.length()){
                //去掉无效字符
                while(desHash[s.charAt(start)]>srcHash[s.charAt(start)]){
                    desHash[s.charAt(start)]--;
                    start++;
                }
                //比较是否为最小
                if(i-start<minLen){
                    minLen=i-start;
                    begin=start;
                    end=i;
                }
                // 把开头的这个匹配字符跳过，为寻找下一个有效窗口准备
                desHash[s.charAt(start)]--;
                found--;
                start++;
            }
        }
        //ensure
        return (begin==-1)?"":s.substring(begin,end+1);
    }
}