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).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

Java代码

/**
 * <p>创建日期：2020-05-23 9:00</p>
 *
 * @author PengHao
 */
class Solution {
    
    public String minWindow(String s, String t) {
    
        char[] sArr = s.toCharArray();

        Map<Character, Integer> window = new HashMap<>(t.length() >> 1);
        Map<Character, Integer> tMap = new HashMap<>(t.length() >> 1);
        // 初始化Map
        for (char ch : t.toCharArray()) {
    
            tMap.put(ch, tMap.getOrDefault(ch, 0) + 1);
        }

        // 滑动窗口中满足条件且不重复的字符个数
        int numOfValidUnrepeatedCharInWindow = 0;
        // 窗口边界，[left, right)
        int left = 0, right = 0;
        // 最小覆盖子串的起始索引和长度
        int minLeft = 0, minLen = s.length() + 1;
        // 扩大窗口
        while (right < s.length()) {
    
            // 进入窗口的字符，并右移窗口右边界
            char enterChar = sArr[right++];
            // 判断字符串t中是否有该字符
            if (tMap.containsKey(enterChar)) {
    
                // 如果有该字符，更新数据
                // 窗口中该字符个数加1
                window.put(enterChar, window.getOrDefault(enterChar, 0) + 1);
                // 判断窗口中该字符的个数是否等于满足条件
                if (window.get(enterChar).equals(tMap.get(enterChar))) {
    
                    // 满足条件，个数加1
                    numOfValidUnrepeatedCharInWindow++;
                }
            }
            // 判断窗口是否满足缩小的条件
            while (numOfValidUnrepeatedCharInWindow == tMap.size()) {
    
                // 判断当前窗口长度是否小于最小长度
                if (minLen > right - left) {
    
                    minLen = right - left;
                    minLeft = left;
                }
                // 移出窗口的字符，并右移窗口左边界
                char outChar = sArr[left++];
                // 判断窗口中是否有该字符
                if (window.containsKey(outChar)) {
    
                    // 判断该字符个数是否刚好满足条件
                    if (window.get(outChar).equals(tMap.get(outChar))) {
    
                        // 不满足条件，个数减1
                        numOfValidUnrepeatedCharInWindow--;
                    }
                    // 字符个数减1
                    window.put(outChar, window.get(outChar) - 1);
                }
            }
        }
        return minLeft + minLen > s.length() ? "" : s.substring(minLeft, minLeft + minLen);
    }
}

参考

1. 我写了一首诗，把滑动窗口算法变成了默写题 - labuladong