问题

76.最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1

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

练习

最小覆盖子串

# your python code

思路

北海啊，要多想！

字符个数匹配

采用 双指针滑动窗口 结合 哈希表记录字符频次 的策略：

• 定义一个哈希表 map：存储 t 中各字符的 剩余待匹配次数（如 t="AAB" 则 map={A:2, B:1}）。
• 定义变量 match：动态追踪当前窗口内 已满足匹配条件的字符数量。

考虑窗口的拓展和收缩：

• 右指针扩展窗口：
  • 当 s[r] 属于 t 时，减少 map 中该字符的计数。
  • 若该字符计数减 1 后仍 ≥0，说明此字符匹配需求未超额，则 match++。
• 左指针收缩窗口：
  当 match == t.length() 时，当前窗口已覆盖 t：
  • 更新最小窗口边界 ansL/R。
  • 左移左指针 l：若移出字符属于 t，则增加其在 map 的计数。
  • 若移出后该字符计数 >0（说明窗口不再满足覆盖条件），则 match--，终止收缩。

Java

import java.util.HashMap;  
import java.util.Scanner;  
  
public class LC76MinWindow {  
    public static void main(String[] args) {  
        // Scanner scanner = new Scanner(System.in);  
        // String s = scanner.nextLine();        
        // String t = scanner.nextLine();  
        
        String s = "ADOBECODEBANC";  
        String t = "ABC";  
  
        System.out.println(minWindow(s, t));  
    }  
    private static String minWindow(String s, String t) {  
        int ansL = -1, ansR = -1;  
        int m = s.length(), n = t.length();  
        HashMap<Character, Integer> map = new HashMap<>();  
  
        for (int i = 0; i < n; i++) {  
            char ch = t.charAt(i);  
            map.put(ch, map.getOrDefault(ch, 0) + 1);  
        }  
        int l = 0, r = 0;  
        int match = 0, matchMax = n;  
        while (r < m) {  
            char ch = s.charAt(r);  
  
            if (map.containsKey(ch)) {  
                map.put(ch, map.get(ch) - 1);  
  
                if (map.get(ch) >= 0) {  
                    match++;  
                }  
                while (match == matchMax) {  
                    if (ansL == -1 || (r - l) < (ansR - ansL)) {  
                        ansL = l;  
                        ansR = r;  
                    }  
                    ch = s.charAt(l);  
                    if (map.containsKey(ch)) {  
                        map.put(ch, map.get(ch) + 1);  
  
                        if (map.get(ch) > 0) {  
                            match--;  
                        }                    
                    }                    
                    l++;  
                }            
            }            
            r++;  
        }  
        return ansL == -1 ? "" : s.substring(ansL, ansR + 1);  
    }
}

复杂度分析：

• 时间复杂度：$\mathcal{O}(m+n)$。
• 空间复杂度：$\mathcal{O}(\lvert \Sigma \rvert)$。$\Sigma$ 表示字符集。