Day 64, #76, Minimum Window Substring

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).
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 emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
-----------------------------------------------------------------------------

## 注意第14行，当前char如果为不需要时，直接跳过。第22行类似。围绕着t里面的字符
## 当发现至少存在一个符合substring时，count一直保持为0

O(n)
------ Explanation here ---------

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> needed(256,0);
        vector<int> owned(256,0);
        for (int i = 0; i < t.length(); i++) {
            needed[t[i]]++; 
        }
        
        int count = t.length();
        int start = 0;
        string rt = "";
        for (int i = 0; i < s.length(); i++) {
            if (needed[s[i]] == 0) continue;
            owned[s[i]]++;
            if (owned[s[i]] <= needed[s[i]]) {
                if (count == t.length()) start = i;
                count--;
            }
            
            if (count == 0) {
                while (needed[s[start]] == 0 || owned[s[start]] > needed[s[start]]) {
                    if (owned[s[start]] > needed[s[start]]) {
                        owned[s[start]]--;
                    }
                    start++;
                }
                if (rt == "" || rt.length() > i - start + 1) {
                    rt = s.substr(start,i - start + 1);
                }
            }
        }
        
        return rt;
    }
};

Java版，总体思路一样，实现上有一点出入
ToDo 扩展阅读，解决所有substring的通用方法：https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems

class Solution {
    public String minWindow(String s, String t) {
        int[] needed = getMap(t);
        int[] sofar = new int[256];
        int count = t.length();
        
        int start = -1;
        String rt = "";
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i);
            sofar[c]++;
            if (needed[c] > 0 && sofar[c] <= needed[c]) {
                count--;
                if (start == -1) start = i;
            }
            while (start != -1 && sofar[s.charAt(start)] > needed[s.charAt(start)]) {
                sofar[s.charAt(start)]--;
                start++;
            }
            if (count == 0 && (i - start + 1 < rt.length() || rt == "")) {
                rt = s.substring(start,i + 1);
            }
        }
            
        return rt;
    }
    
    private int[] getMap(String t) {
        int[] map = new int[256];
        for (int i = 0; i < t.length(); i++) {
            map[t.charAt(i)]++;
        }
        
        return map;
    }
}