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

Notice

If there is no such window in source that covers all characters in target, return the emtpy string"".

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

Have you met this question in a real interview?

Yes

Clarification

Should the characters in minimum window has the same order in target?

  • Not necessary.

Example

For source ="ADOBECODEBANC", target ="ABC", the minimum window is"BANC"

Challenge

Can you do it in time complexity O(n) ?

line 42 const smap can't use operator [] , should use operator at

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

 \*/

typedef unordered\_map<char,int> Map;



string minWindow\(string &source, string &target\) {

    // write your code here

    string res = "";

    if \( source.length\(\) < target.length\(\) \) {

        return res;

    }

    int i = 0, j = 0, len = INT\_MAX;



    Map tmap, smap;

    for \(auto& ch : target\) {

        tmap\[ch\]++;

    }

    for \(i = 0; i < source.length\(\); ++i\) {

        while \( j < source.length\(\) && !cover\(smap, tmap\) \)             {

            ++smap\[ source\[j\] \];

            ++j;

        }

        if \( cover\(smap, tmap\) \) {

            if \(len > j - i\) {

                len = j - i;

                res =  source.substr\(i, len\);

            }

        }

        --smap\[source\[i\]\];

    }

    return res;

}

private:

bool cover\(const Map& smap, const Map& tmap\) {

    for \(auto& x : tmap\) {

        if \( smap.find\(x.first\) == smap.end\(\) \|\|

             smap.at\(x.first\) < x.second\) {

                return false;

        }

    }

    return true;

}

};

results matching ""

    No results matching ""