Minimum Window Substring

Given a string source and a string target, find the minimum window in source which will contain all the characters in target.

http://www.lintcode.com/en/problem/minimum-window-substring/

Discussion

一个字符串是否包另一个字符串中的所有字符，有一个单独的题，不难。那扩展一下就是对source里面的每个substring，判断它是否包含target里面的所有字符。这需要耗费O(N^3)的时间。然后找出最短的substring。

Solution

class Solution {
public:    
    /**
     * @param source: A string
     * @param target: A string
     * @return: A string denote the minimum window
     *          Return "" if there is no such a string
     */
    string minWindow(string &source, string &target) {
        string min_win;
        if(source.length() == 0) return min_win;
        int n = source.length();
        vector<vector<bool> > i_contains(n, vector<bool>(n, false));
        int m = target.length();
        if(n < m) return min_win;
        //check if [i,j] in source contains target
        for(int i=0; i<n; i++) {
            bool contained = false;
            for(int j=i+m-1; j<n; j++) {
                if(contained || contains(source, target, i, j)) {
                    i_contains[i][j] = true;
                    contained = true;
                }
            }
        }
        //get the min window
        int min_start = 0; 
        int min_len = n+1;
        for(int i=0; i<n; i++) {
            if(i_contains[i][n-1] == false) 
            {
                break;
            }
            for(int j=i+m-1; j<n; j++) {
                if(i_contains[i][j]) {
                    if(j-i+1 < min_len) {
                        min_len = j-i+1;
                        min_start = i;
                    }
                    break; //don't need to check later in this row
                }
            }
        }
        if(min_len == n+1) return min_win; //return empty
        return source.substr(min_start, min_len);
    }
    //[start, end] in source contains target
    bool contains(string &source, string &target, int start, int end) {
        int cnt[256] = {0};
        for(int i=start; i<=end; i++) {
            cnt[source[i]]++;
        }
        for(auto const& c : target) {
            cnt[c]--;
            if(cnt[c]<0) {
                return false;
            }
        }
        return true;
    }
};

Follow up

很明显上面调用contains的时候有重复判断，就跟palindrome那个题一样，只不过那个是判断首尾字符可以去掉重复判断，这里要去重就需要统计每个字符出现的次数，用start end两个指针，move end当target里所有字符都出现的时候，move start，知道不是所有字符都出现。

class Solution {
public:    
    /**
     * @param source: A string
     * @param target: A string
     * @return: A string denote the minimum window
     *          Return "" if there is no such a string
     */
    string minWindow(string &source, string &target) {
        if(source.length() == 0) return "";
        int n = source.length();
        int m = target.length();
        if(n < m) return "";
        int min_start = 0;
        int min_win_len = n+1;
        const int ASCII = 256;
        //get freqency of each char in target
        int freq_target[ASCII] = {0};
        for(auto const& c : target) {
            freq_target[c]++;
        }
        //get the freqency of those chars in source, compare with target at the same time
        int freq_source[ASCII] = {0};
        int counter = 0;
        int start = 0;
        for(int i=0; i<n; i++) {
            char c  = source[i];
            if(freq_target[c] >0) {//means source[i] is in target
                freq_source[c]++;
                if(freq_source[c] <= freq_target[c]) {
                    counter++;
                }
            }
            if(counter == m) {//all chars in target appear
                while(freq_target[source[start]] == 0 || //source[start] is not in target
                freq_source[source[start]] > freq_target[source[start]]) {//source[start] appears too many times
                    freq_source[source[start]]--;
                    start++; //move start pointer
                }
                //update min window
                if(i-start+1 < min_win_len) {
                    min_win_len = i-start+1;
                    min_start = start;
                }
            }
        }
        //output min window
        if(min_win_len == n+1) return "";
        return source.substr(min_start, min_win_len);
    }
};