76. Minimum Window Substring

Question

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"

Thinking:

• Method 1:双指针 TLE

class Solution {
    public String minWindow(String s, String t) {
        if(s == null || t == null) return "";
        int min = Integer.MAX_VALUE;
        String result = "";
        int sLen = s.length();
        int tLen = t.length();
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        Map<Character, Integer> cmp = new HashMap<>();
        for(int i = 0; i < tLen; i++)
            cmp.put(tArr[i], cmp.containsKey(tArr[i]) ? cmp.get(tArr[i]) + 1: 1);
        for(int i = 0; i <= sLen - tLen; i++){
            if(!cmp.containsKey(sArr[i])) continue;
            Map<Character, Integer> temp = new HashMap<>();
            temp.put(sArr[i], 1);
            if(check(temp, cmp)){
                result = s.substring(i, i + 1);
                min = 1;
                return result;
            }
            for(int j = i + 1; j < sLen; j++){
                if(!cmp.containsKey(sArr[j])) continue;
                temp.put(sArr[j], temp.containsKey(sArr[j])?temp.get(sArr[j]) + 1: 1);
                if(check(temp, cmp)){
                    if(j - i + 1 < min){
                        min = j - i + 1;
                        result = s.substring(i, j + 1);
                    }
                    break;
                }
            }
        }
        return result;
    }
    private static boolean check(Map<Character, Integer> sMap, Map<Character, Integer> tMap){
        Set<Character> set = tMap.keySet();
        for(Character c : set){
            if(!sMap.containsKey(c)) return false;
            else
                if(sMap.get(c) < tMap.get(c)) return false;
        }
        return true;
    }
}

• Method 2: 滑动窗口

class Solution {
    public String minWindow(String s, String t) {
        if(s == null || t == null) return "";
        int[] sMap = new int[256];
        int[] tMap = new int[256];
        int sLen = s.length();
        int tLen = t.length();
        for(int i = 0; i < tLen; i++)
            tMap[t.charAt(i)]++;
        int right = 0;
        String result = "";
        int min = Integer.MAX_VALUE;
        for(int i = 0; i <= sLen - tLen; i++){
            while(right < sLen && !check(sMap, tMap)){
                sMap[s.charAt(right)]++;
                right++;
            }
            if(check(sMap, tMap) && min > right - i + 1){
                min = right - i + 1;
                result = s.substring(i, right);
            }
            sMap[s.charAt(i)]--;
        }
        return result;
    }
    private boolean check(int[] sMap, int[] tMap){
        for(int i = 0; i < sMap.length; i++){
            if(tMap[i] > sMap[i])
                return false;
        }
        return true;
    }
}

二刷

这道题还是借鉴了一刷时候的结果，我先写出来了双指针的方法，最后一个test case无法通过。所以换成了滑动窗口的解法，最后AC。

class Solution {
    public String minWindow(String s, String t) {
        if(s == null || t == null) return "";
        String result = "";
        int res = s.length() + 1;
        int[] tMap = new int[128];
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        for(int i = 0; i < tArr.length; i++)
            tMap[tArr[i]]++;
        int[] cmp = new int[128];
        int right = 0;
        for(int i = 0; i <= sArr.length - tArr.length; i++){
            while(right < sArr.length && !same(tMap, cmp)){
                cmp[sArr[right++]]++;
            }
            if(same(tMap, cmp) && right - i + 1 <= res){
                res = right - i + 1;
                result = s.substring(i, right);
            }
            cmp[sArr[i]]--;
        }
        return result;
    }
    private boolean same(int[] a, int[] b){
        for(int i = 0; i < 128; i++)
            if(a[i] != 0 && b[i] < a[i])
                return false;
        return true;
    }
}