76. Minimum Window Substring

题目描述和难度

• 题目描述：

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

• 题目难度：困难。
• 英文网址：76. Minimum Window Substring 。
• 中文网址：76. 最小覆盖子串 。

思路分析

求解关键：使用滑动窗口的思想，并且使用两个字符计数数组。先复习第 438 题再做这题可能会好些，解决它们都用了相同的策略。

• S 的字符计数数组记录了当前滑动窗口包括的字符的个数，是动态变化的。
• T 的字符计数数组记录了字符串 T 中的字符的个数，扫描过一次以后这个数组我们不去动它，用来和 S 的字符计数数组进行对应位置上的比较。

参考解答

参考解答1

import java.util.HashSet;
import java.util.Set;

public class Solution {

    public String minWindow(String s, String t) {
        int[] cntS = new int[256];
        int[] cntT = new int[256];

        Set<Character> set = new HashSet<>();
        // cntT 赋值了以后，就成为了用于比对的对象，不更新
        for (char ct : t.toCharArray()) {
            cntT[ct]++;
            set.add(ct);
        }

        int minSub = s.length() + 1;
        String res = "";
        int left = 0;
        int right = 0;
        int count = 0;
        while (right < s.length()) {
            char rc = s.charAt(right);
            if (!set.contains(rc)) {
                // 不在字典里面，但是右边界同样要扩充，所以 right++
                right++;
                continue;
            }
            cntS[rc]++;
            right++;
            // 理解这里是关键：加上以后，小于等于，count 才 ++，
            if (cntS[rc] <= cntT[rc]) {
                // count++; 这件事情说明滑动窗口里面的有效字符，向目标字符又近了一步
                count++;
            }

            // 下面这一段可以写得更精简一些，但是为了语义上的清晰，我就写得冗长一些
            if (count == t.length()) {
                // 接下来，考虑左边界移出滑动窗口
                // 不在字典中，或者多了的时候，直接划掉就可以了
                while (true) {
                    char deleteChar = s.charAt(left);
                    if (!set.contains(deleteChar)) {
                        left++;
                        continue;
                    }
                    if (cntS[deleteChar] > cntT[deleteChar]) {
                        cntS[deleteChar]--;
                        left++;
                        continue;
                    }
                    break;
                }
                if (right - left < minSub) {
                    minSub = right - left;
                    res = s.substring(left, right);
                }
            }
        }
        if (minSub == s.length() + 1) {
            return "";
        }
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String S = "ADOBECODEBANC";
        String T = "ABC";
        String minWindow = solution.minWindow(S, T);
        System.out.println(minWindow);
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0076-minimum-window-substring ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。