Problem

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

For example,
S="ADOBECODEBANC"
T="ABC"

Minimum window is"BANC".

Note:
If there is no such window in S that covers all characters in T, return the empty string"".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

思路

• O(n) time complexity requirement
• question:
  • are there any duplicate characters in string T ?
    • if yes, we need a counter
• if [end] in T, counter--
  • (special case: duplicate in S, unique in T, need to filter redundant char)
    • only when table([end]) >= 0, counter--.

•   /*
        1. hash table
            A:1
            B:1
            N:1
            C:1
  
        2. counter      4
        3. length       6
        4. substring    "ADOBEC"
        5. start        ++
    */
    public String minWindow(String s, String t) {
        if (s == null || t == null) {
            return "";
        }
        HashMap<Character, Integer> table = new HashMap<>();
        int counter = t.length();
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            table.put(c, table.getOrDefault(c, 0) + 1);
        }
        int minLength = s.length();
        String res = "";
        int end = 0;
        int start = 0;
  
        while (end < s.length()) {
            char ce = s.charAt(end);
            if (table.containsKey(ce)) {
                table.put(ce, table.get(ce) - 1);
                if (table.get(ce) >= 0) {
                    counter--;    
                }
            }
            end++;
            while (counter == 0) {
                char cs = s.charAt(start);
                if (table.containsKey(cs)) {
                    if (table.get(cs) >= 0) {
                        counter++;   
                    }
                    table.put(cs, table.get(cs) + 1);
                }
                if (minLength >= end - start) {
                    minLength = end - start;
                    res = s.substring(start, end);
                }
                start++;
            }
        }
        return res;
    }