困难 · 子串 · 原题

题目信息

LeetCode #76 · Minimum Window Substring

标签：哈希表、字符串、滑动窗口

题目要求

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。

测试用例保证答案唯一。

示例 1：

1
2
3
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

1
2
3
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

1
2
3
4
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

  • m == s.length

  • n == t.length

  • 1 <= m, n <= 10^5

  • s 和 t 由英文字母组成

进阶：你能设计一个在 O(m + n) 时间内解决此问题的算法吗？

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:

    bool is_covered(int cnt_s[],int cnt_t[]){
        for(int i='a';i<='z';i++){
            if(cnt_s[i]<cnt_t[i]) return false;
        }
        for(int i='A';i<='Z';i++){
            if(cnt_s[i]<cnt_t[i]) return false;
        }
        return true;
    }

    string minWindow(string s, string t) {
        int cnt_s[128]{};
        int cnt_t[128]{};
        int ans_left=-1,ans_right=s.size();
        for(int i=0;i<t.size();i++) cnt_t[t[i]]++;
        for(int left=0,right=0;right<s.size();right++){
            cnt_s[s[right]]++;
            while(is_covered(cnt_s,cnt_t)){
                if(ans_right-ans_left>right-left){
                    ans_right=right;ans_left=left;
                }
                cnt_s[s[left]]--;left++;
            }
        }
        return ans_left==-1?"":s.substr(ans_left,ans_right-ans_left+1);
    }
};

返回目录