最小覆盖子串

76. 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明：

• 如果 S 中不存这样的子串，则返回空字符串 ""。
• 如果 S 中存在这样的子串，我们保证它是唯一的答案。

我们可以用滑动窗口的思想解决这个问题，在滑动窗口类型的问题中都会有两个指针。一个用于延伸现有窗口的 right 指针，和一个用于收缩窗口的 left 指针。在任意时刻，只有一个指针移动，另一个保持静止。我们在 s 上滑动窗口，通过 right 指针不断扩张窗口，当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩直到得到最小窗口。

如何判断滑动窗口[left,right)是否包含字符串 t 中所有字符呢？当让我们可以暴力统计，但这样效率太低。我们使用两个辅助数组 ，winFreq 表示窗口中的字符统计数组，tFreq 表示字符串 t 中的字符统计数组。维护变量 distance，表示滑动窗口内部包含了 t 中字符的个数，窗口内单个字符个数等于 t 中对应字符个数时不再增加。

class Solution {
    public String minWindow(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if(sLen == 0 || tLen == 0 || tLen > sLen){
            return "";
        }

        char[] charArrayS = s.toCharArray();
        char[] charArrayT = t.toCharArray();

        int[] winFreq = new int[128];
        int[] tFreq = new int[128];
        for(char c : charArrayT){
            tFreq[c] ++ ;
        }

        //distance 表示滑动窗口内部包含了 t 中字符的个数，窗口内单个字符个数等于 t 中对应字符个数时不再增加
        int distance = 0;
        int minLen = sLen + 1;
        int begin = 0;
        int left = 0;
        int right = 0;
        //[left, right)滑动窗口长度

        while(right < sLen){
            char charRight = charArrayS[right];

            //右边界元素在 t 中不出现
            if(tFreq[charRight] == 0){
                right++;
                continue;
            }

            //右边界元素在 t 中出现
            if(winFreq[charRight] < tFreq[charRight]){
                distance++;
            }
            //窗口字符减一，窗口右边界右移
            winFreq[charRight]++;
            right++;

            //左边界向右移动，滑动窗口此时已经包含 t 中所有字符
            while(distance == tLen){
                //统计最小子串的开始位置及长度
                if(right - left < minLen){
                    minLen = right - left;
                    begin = left;
                }

                //左边界元素在 t 中没有出现
                char charLeft = charArrayS[left];
                if(tFreq[charLeft] == 0){
                    left++;
                    continue;
                }
                //左边界元素在 t 中出现
                if(winFreq[charLeft] == tFreq[charLeft]){
                    distance--;
                }
                //窗口字符减一，窗口左边界右移
                winFreq[charLeft]--;
                left++;
            }
        }

        if(minLen == sLen + 1){
            return "";
        }
        return s.substring(begin, begin + minLen);
    }
}

我们可以优化空间只使用 tFreq 一个数组，将 distance 设置为 tLen ，对distance 使用减法，当distance == 0时表示窗口中含有字符串 t 中所有字符。

class Solution {
    public String minWindow(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if(sLen == 0 || tLen == 0 || tLen > sLen){
            return "";
        }

        char[] charArrayS = s.toCharArray();
        char[] charArrayT = t.toCharArray();

        int[] tFreq = new int[128];
        for(char c : charArrayT){
            tFreq[c] ++ ;
        }

        //distance 表示滑动窗口内部包含了 t 中字符的个数，窗口内单个字符个数等于 t 中对应字符个数时不再增加
        int distance = tLen;
        int minLen = sLen + 1;
        int begin = 0;
        int left = 0;
        int right = 0;
        //[left, right)滑动窗口长度

        
        while(right < sLen){
            char charRight = charArrayS[right];

            //右边界元素在 t 中出现
            if(tFreq[charRight] > 0){
                distance--;
            }
            tFreq[charRight]--;
            right++;

            //左边界向右移动，滑动窗口此时已经包含 t 中所有字符
            while(distance == 0){
                //统计最小子串的开始位置及长度
                if(right - left < minLen){
                    minLen = right - left;
                    begin = left;
                }

                //左边界元素在 t 中出现
                char charLeft = charArrayS[left];
                if(tFreq[charLeft] == 0){
                    distance++;
                }
                tFreq[charLeft]++;
                left++;
            }
        }

        if(minLen == sLen + 1){
            return "";
        }
        return s.substring(begin, begin + minLen);
    }
}