LeetCode 0076 - Minimum Window Substring

Reck Zhang

发布于 2021-08-11 10:47:53

3530

发布于 2021-08-11 10:47:53

文章被收录于专栏：Reck Zhang

Minimum Window Substring

Desicription

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.

Solution

class Solution {
public:
    string minWindow(string s, string t) {
        if(s.empty() || t.empty())
            return "";
        int cnt = t.size();
        vector<int> require(128, 0);
        vector<bool> book(128, 0);
        for(int i = 0; t[i]; ++i)
            require[t[i]]++, book[t[i]] = 1;
        int left = 0;
        int right = -1;
        int min_len = INT_MAX;
        int min_index = 0;
        while(left < s.size() && right < (int)s.size()){
            if(cnt){
                require[s[++right]]--;
                if(book[s[right]] && require[s[right]] >= 0)
                    cnt--;
            }
            else{
                if(min_len > right - left + 1)
                    min_len = right - left + 1, min_index = left;
                require[s[left]]++;
                if(book[s[left]] && require[s[left]] > 0)
                    cnt++;
                left++;
            }
        }
        if(min_len == INT_MAX)
            return "";
        return s.substr(min_index, min_len);
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-11-19，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度