Leetcode 76 Minimum Window Substring 最小窗口子串

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.

题意分析

从复杂性的角度看，本题的理想情况下应该在一遍扫描中完成，假设S的长度为m，T的长度为n，直觉上认为本题最终解释的复杂性不应该高于 O(m+n).

思路1

对于S从左往右扫描，只扫描出现在T中的字符，同时维护一个hashmap用于记录当前扫描到的子串情况。对于单次扫描的结果，将新遇到的字符加入map之中，同时分析是否可将子串靠前的部分删除。

class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character,Integer> target = new HashMap<>();
        HashMap<Character,Integer> source = new HashMap<>();
        int count = 0;
        List<Integer> pos = new ArrayList<>();
        int minLength = Integer.MAX_VALUE;
        String minWindow = "";

        for (int i=0;i<t.length();i++){
            char ch = t.charAt(i);
            target.put(ch,target.getOrDefault(ch,0)+1);
        }

        for (int i=0;i<s.length();i++){

            char ch = s. charAt(i);
            if (!target.containsKey(ch)) continue;

            //Add new target character
            int freqTarget = target.get(ch);
            int freqSource = source.getOrDefault(ch,0);
            source.put(ch,freqSource+1);
            pos.add(i);
            if (freqTarget>freqSource) count++;

            //Check whether we could remove old character
            ch = s.charAt(pos.get(0));
            freqTarget = target.get(ch);
            freqSource = source.get(ch);
            while (freqTarget<freqSource){
                pos.remove(0);
                source.put(ch,freqSource-1);
                ch = s.charAt(pos.get(0));
                freqTarget = target.get(ch);
                freqSource = source.get(ch);
            }

            if (count==t.length() && i-pos.get(0)<minLength){
                minWindow = s.substring(pos.get(0),i+1);
                minLength = i-pos.get(0);
            }

        }
        return minWindow;


    }
}

上述代码维护了两个hashmap，一个用于记录target的出现频次，另一个用于记录source的出现频次，并且比较两者之间的频次，决定是否加入或者删除。一个平凡的改进即只使用一个hashmap记录两者之间的差值。

class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character,Integer> freqs = new HashMap<>();
        int count = 0;
        List<Integer> pos = new ArrayList<>();
        int minLength = Integer.MAX_VALUE;
        String minWindow = "";

        for (int i=0;i<t.length();i++){
            char ch = t.charAt(i);
            freqs.put(ch,freqs.getOrDefault(ch,0)+1);
        }

        for (int i=0;i<s.length();i++){

            char ch = s. charAt(i);
            if (!freqs.containsKey(ch)) continue;

            //Add new target character
            int freq = freqs.get(ch);
            freqs.put(ch,freq-1);
            pos.add(i);
            if (freq>0) count++;

            //Check whether we could remove old character
            ch = s.charAt(pos.get(0));
            freq = freqs.get(ch);
            while (freq<0){
                pos.remove(0);
                freqs.put(ch,freq+1);
                ch = s.charAt(pos.get(0));
                freq = freqs.get(ch);
            }

            if (count==t.length() && i-pos.get(0)<minLength){
                minWindow = s.substring(pos.get(0),i+1);
                minLength = i-pos.get(0);
            }
        }
        return minWindow;
    }
}