76. 最小覆盖子串

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

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

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：

输入：s = "a", t = "a"
输出："a"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

参考：https://github.com/labuladong/fucking-algorithm/blob/master/%E7%AE%97%E6%B3%95%E6%80%9D%E7%BB%B4%E7%B3%BB%E5%88%97/%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%8A%80%E5%B7%A7.md

类似于： https://www.jianshu.com/p/1d471d9a6a81

public String minWindow(String s, String t) {

        int left = 0;
        int right = 0;   // 构建 arr[left,right] 滑动窗口

        char[] sourceCharArray = s.toCharArray();
        char[] targetCharArray = t.toCharArray();

        //计数器
        int[] sourceFreq = new int[256];
        int[] targetFreq = new int[256];

        //将目标录入到目标计数器
        for (int i = 0; i < t.length(); i++) {
            targetFreq[targetCharArray[i]]++;
        }

        //目标总数
        int total = t.length();

        int start = 0;
        int end = s.length() + 1;

        while (right < s.length()) {
            char currentIndex = sourceCharArray[right];

            if (targetFreq[currentIndex] > 0) {
                sourceFreq[currentIndex]++;
                //如果 计数一致 则减少目标总数 total 避免重复元素重复计数
                if (sourceFreq[currentIndex] <= targetFreq[currentIndex]) {
                    total--;
                }
            }

            while (total == 0) {
                char leftIndex = sourceCharArray[left];
                if ((right - left + 1) >= targetCharArray.length && (right - left) < (end - start)) {
                    start = left;
                    end = right;
                }
                if (targetFreq[leftIndex] > 0) {
                    sourceFreq[leftIndex]--;

                    //如果 计数一致 则增加目标总数 total  避免重复元素重复计数
                    if (sourceFreq[leftIndex] < targetFreq[leftIndex]) {
                        total++;
                    }
                }

                left++;
            }

            right++;
        }

        //如果 end start 没有变化则返回 空
        if ((end - start) == (s.length() + 1)) {
            return "";
        }

        return s.substring(start, end + 1);
    }

解法相同的 还有

242. 有效的字母异位词

public boolean isAnagram(String s, String t) {
        char[] sourceArr = s.toCharArray();
        char[] targetArr = t.toCharArray();

        if (sourceArr.length != targetArr.length) {
            return false;
        }

        int[] sourceFreq = new int[256];
        int[] targetFreq = new int[256];

        for (int i = 0; i < targetArr.length; i++) {
            targetFreq[targetArr[i]]++;
        }

        int total = sourceArr.length;


        int left = 0;
        int right = 0;

        while (right < sourceArr.length) {
            char currentCharIndex = sourceArr[right];
            if (targetFreq[currentCharIndex] <= 0) {
                return false;
            }

            sourceFreq[currentCharIndex]++;
            if (sourceFreq[currentCharIndex] <= targetFreq[currentCharIndex]) {
                total--;
            } else {
                return false;
            }


            while (total == 0) {
                char leftCharIndex = sourceArr[left];
                if (targetFreq[leftCharIndex] <= 0) {
                    return false;
                }

                sourceFreq[leftCharIndex]--;
                if (sourceFreq[leftCharIndex] <= targetFreq[leftCharIndex]) {
                    total++;
                }
                left++;
            }

            right++;
        }

        return true;
    }