法算day12

[up主专用，视频内嵌代码贴在这]

最小覆盖子串

问题描述

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

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

  • 示例 1：
    输入：s = “ADOBECODEBANC”, t = “ABC”
    输出：”BANC”
    解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、’B’ 和 ‘C’。

  • 示例 2：
    输入：s = “a”, t = “a”
    输出：”a”
    解释：整个字符串 s 是最小覆盖子串。

  • 示例 3:
    输入: s = “a”, t = “aa”
    输出: “”
    解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
    因此没有符合条件的子字符串，返回空字符串。

提示：
m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母组成

算法分析

这是一个典型的滑动窗口问题，需要在字符串s中找到包含字符串t所有字符的最小子串。算法使用了双指针技巧和哈希表来高效解决这个问题。

  1. 初始化阶段
    1
    2
    need_dict = defaultdict(int)  # 记录t中每个字符的出现次数
    window_dict = defaultdict(int)  # 记录当前窗口中每个字符的出现次数
  • need_dict：统计目标字符串t中每个字符的出现频率
  • window_dict：统计当前滑动窗口中每个字符的出现频率
  1. 滑动窗口过程
    算法通过两个指针left和right维护一个滑动窗口：
  • 扩展窗口（右指针移动）：
    右指针向右移动，将新字符加入窗口
    更新窗口字符计数
    如果当前字符在t中，并且窗口中该字符的数量等于t中该字符的数量，则增加有效计数valid
  • 收缩窗口（左指针移动）：
    当窗口包含t的所有字符时（valid == len(need_dict)）
    尝试收缩左指针，寻找更小的满足条件的窗口
    更新最小窗口记录
    如果移出的字符在t中，更新窗口计数和有效计数
  1. 终止条件
  • 右指针遍历完整个字符串s
  • 返回找到的最小窗口子串

算法关键点

  1. 滑动窗口策略：
    右指针扩展窗口，直到包含t的所有字符
    左指针收缩窗口，寻找最小满足条件的窗口

  2. 有效计数机制：
    只有当窗口中某个字符的数量恰好等于t中该字符的数量时，才增加valid
    这确保了valid准确反映窗口是否包含t的所有字符

  3. 最小窗口更新：
    每次找到满足条件的窗口时，记录并更新最小窗口
    通过收缩窗口寻找更小的满足条件的窗口

python版

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
from collections import defaultdict

def minWindow(s, t):
    """
    找到s中涵盖t所有字符的最小子串
    
    参数:
        s: 主字符串
        t: 目标字符串
        
    返回:
        str: 最小覆盖子串，如果不存在则返回空字符串
    """
    # 如果s或t为空，或者s的长度小于t的长度，直接返回空字符串
    if not s or not t or len(s) < len(t):
        return ""
    
    # 使用defaultdict记录t中每个字符的出现次数
    need_dict = defaultdict(int)
    for char in t:
        need_dict[char] += 1
    
    # 使用defaultdict记录当前窗口中每个字符的出现次数
    window_dict = defaultdict(int)
    
    # 初始化左右指针、有效字符计数、最小窗口的起始位置和长度
    left = 0
    right = 0
    valid = 0  # 记录窗口中满足need_dict要求的字符数量
    start = 0  # 最小窗口的起始位置
    min_len = float('inf')  # 最小窗口长度，初始化为无穷大
    
    # 滑动窗口，右指针遍历整个字符串s
    while right < len(s):
        # 获取右指针指向的字符
        c = s[right]
        # 右指针向右移动
        right += 1
        
        # 如果当前字符在t中，则更新窗口计数
        if c in need_dict:
            window_dict[c] += 1
            # 如果窗口中该字符的数量等于t中该字符的数量，则有效计数加1
            if window_dict[c] == need_dict[c]:
                valid += 1
        
        # 当窗口中包含t的所有字符时，尝试收缩左指针
        while valid == len(need_dict):
            # 更新最小窗口
            if right - left < min_len:
                start = left
                min_len = right - left
            
            # 获取左指针指向的字符
            d = s[left]
            # 左指针向右移动
            left += 1
            
            # 如果移出的字符在t中，则更新窗口计数
            if d in need_dict:
                # 如果窗口中该字符的数量等于t中该字符的数量，则有效计数减1
                if window_dict[d] == need_dict[d]:
                    valid -= 1
                window_dict[d] -= 1
    
    # 如果找到了最小窗口，返回对应的子串，否则返回空字符串
    return "" if min_len == float('inf') else s[start:start + min_len]

# 测试代码
if __name__ == "__main__":
    # 示例1
    s1 = "ADOBECODEBANC"
    t1 = "ABC"
    print(f"输入: s = '{s1}', t = '{t1}'")
    print(f"输出: '{minWindow(s1, t1)}'")  # 输出: "BANC"
    
    # 示例2
    s2 = "a"
    t2 = "a"
    print(f"输入: s = '{s2}', t = '{t2}'")
    print(f"输出: '{minWindow(s2, t2)}'")  # 输出: "a"
    
    # 示例3
    s3 = "a"
    t3 = "aa"
    print(f"输入: s = '{s3}', t = '{t3}'")
    print(f"输出: '{minWindow(s3, t3)}'")  # 输出: ""

✅ 说明：

  • 时间复杂度：O(n)，其中n是字符串s的长度
  • 空间复杂度：O(m)，其中m是字符集的大小

举例说明s = “ADOBECODEBANC”；t = “ABC”

  • 初始状态
    1
    2
    3
    4
    5
    6
    7
    8
    s: A D O B E C O D E B A N C
    t: A B C

    need_dict: {'A':1, 'B':1, 'C':1}
    window_dict: {}
    left = 0, right = 0
    valid = 0
    min_len = ∞, start = 0
  • 步骤1：right=0, char=’A’
    1
    2
    3
    4
    5
    6
    7
    8
    9
    当前窗口: [A]
    操作:
    - A在need_dict中
    - window_dict['A'] = 1
    - window_dict['A'] == need_dict['A'] (1==1) → valid=1
    状态:
      window_dict: {'A':1}
      valid = 1 (A满足要求)
      不满足条件(valid=1 < 3)，继续扩展
  • 步骤2：right=1, char=’D’
    1
    2
    3
    4
    5
    6
    7
    当前窗口: [A D]
    操作:
    - D不在need_dict中，跳过
    状态:
      window_dict: {'A':1}
      valid = 1
      不满足条件，继续扩展
  • 步骤3：right=2, char=’O’
    1
    2
    3
    4
    5
    6
    7
    当前窗口: [A D O]
    操作:
    - O不在need_dict中，跳过
    状态:
      window_dict: {'A':1}
      valid = 1
      不满足条件，继续扩展
  • 步骤4：right=3, char=’B’
    1
    2
    3
    4
    5
    6
    7
    8
    9
    当前窗口: [A D O B]
    操作:
    - B在need_dict中
    - window_dict['B'] = 1
    - window_dict['B'] == need_dict['B'] (1==1) → valid=2
    状态:
      window_dict: {'A':1, 'B':1}
      valid = 2 (A和B满足要求)
      不满足条件(valid=2 < 3)，继续扩展
  • 步骤5：right=4, char=’E’
    1
    2
    3
    4
    5
    6
    7
    当前窗口: [A D O B E]
    操作:
    - E不在need_dict中，跳过
    状态:
      window_dict: {'A':1, 'B':1}
      valid = 2
      不满足条件，继续扩展
  • 步骤6：right=5, char=’C’
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    当前窗口: [A D O B E C]
    操作:
    - C在need_dict中
    - window_dict['C'] = 1
    - window_dict['C'] == need_dict['C'] (1==1) → valid=3
    状态:
      window_dict: {'A':1, 'B':1, 'C':1}
      valid = 3 (A、B、C都满足要求)
      满足条件(valid=3 == 3)，开始收缩窗口
      
      // 收缩窗口
      当前窗口长度: 6-0=6
      更新最小窗口: min_len=6, start=0
      
      移除left=0的字符'A':
      - A在need_dict中
      - window_dict['A'] == need_dict['A'] (1==1) → valid=2
      - window_dict['A'] = 0
      
      状态:
        window_dict: {'A':0, 'B':1, 'C':1}
        valid = 2
        不满足条件，停止收缩
  • 步骤7：right=6, char=’O’
    1
    2
    3
    4
    5
    6
    7
    当前窗口: [D O B E C O]
    操作:
    - O不在need_dict中，跳过
    状态:
      window_dict: {'A':0, 'B':1, 'C':1}
      valid = 2
      不满足条件，继续扩展
  • 步骤8：right=7, char=’D’
    1
    2
    3
    4
    5
    6
    7
    当前窗口: [D O B E C O D]
    操作:
    - D不在need_dict中，跳过
    状态:
      window_dict: {'A':0, 'B':1, 'C':1}
      valid = 2
      不满足条件，继续扩展
  • 步骤9：right=8, char=’E’
    1
    2
    3
    4
    5
    6
    7
    当前窗口: [D O B E C O D E]
    操作:
    - E不在need_dict中，跳过
    状态:
      window_dict: {'A':0, 'B':1, 'C':1}
      valid = 2
      不满足条件，继续扩展
  • 步骤10：right=9, char=’B’
    1
    2
    3
    4
    5
    6
    7
    8
    9
    当前窗口: [D O B E C O D E B]
    操作:
    - B在need_dict中
    - window_dict['B'] = 2
    - window_dict['B'] > need_dict['B'] (2>1)，valid不变
    状态:
      window_dict: {'A':0, 'B':2, 'C':1}
      valid = 2
      不满足条件，继续扩展
  • 步骤11：right=10, char=’A’
    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
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    当前窗口: [D O B E C O D E B A]
    操作:
    - A在need_dict中
    - window_dict['A'] = 1
    - window_dict['A'] == need_dict['A'] (1==1) → valid=3
    状态:
      window_dict: {'A':1, 'B':2, 'C':1}
      valid = 3 (A、B、C都满足要求)
      满足条件，开始收缩窗口
      
      // 收缩窗口
      当前窗口长度: 11-1=10
      10 > min_len=6，不更新最小窗口
      
      移除left=1的字符'D':
      - D不在need_dict中，跳过
      
      状态:
        window_dict: {'A':1, 'B':2, 'C':1}
        valid = 3
        满足条件，继续收缩
        
      当前窗口长度: 11-2=9
      9 > min_len=6，不更新最小窗口
      
      移除left=2的字符'O':
      - O不在need_dict中，跳过
      
      状态:
        window_dict: {'A':1, 'B':2, 'C':1}
        valid = 3
        满足条件，继续收缩
        
      当前窗口长度: 11-3=8
      8 > min_len=6，不更新最小窗口
      
      移除left=3的字符'B':
      - B在need_dict中
      - window_dict['B'] = 1
      - window_dict['B'] == need_dict['B'] (1==1)，valid不变
      - window_dict['B'] = 1
      
      状态:
        window_dict: {'A':1, 'B':1, 'C':1}
        valid = 3
        满足条件，继续收缩
        
      当前窗口长度: 11-4=7
      7 > min_len=6，不更新最小窗口
      
      移除left=4的字符'E':
      - E不在need_dict中，跳过
      
      状态:
        window_dict: {'A':1, 'B':1, 'C':1}
        valid = 3
        满足条件，继续收缩
        
      当前窗口长度: 11-5=6
      6 == min_len=6，不更新最小窗口
      
      移除left=5的字符'C':
      - C在need_dict中
      - window_dict['C'] == need_dict['C'] (1==1) → valid=2
      - window_dict['C'] = 0
      
      状态:
        window_dict: {'A':1, 'B':1, 'C':0}
        valid = 2
        不满足条件，停止收缩
  • 步骤12：right=11, char=’N’
    1
    2
    3
    4
    5
    6
    7
    当前窗口: [O D E B A N]
    操作:
    - N不在need_dict中，跳过
    状态:
      window_dict: {'A':1, 'B':1, 'C':0}
      valid = 2
      不满足条件，继续扩展
  • 步骤13：right=12, char=’C’
    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
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    当前窗口: [O D E B A N C]
    操作:
    - C在need_dict中
    - window_dict['C'] = 1
    - window_dict['C'] == need_dict['C'] (1==1) → valid=3
    状态:
      window_dict: {'A':1, 'B':1, 'C':1}
      valid = 3 (A、B、C都满足要求)
      满足条件，开始收缩窗口
      
      // 收缩窗口
      当前窗口长度: 13-6=7
      7 > min_len=6，不更新最小窗口
      
      移除left=6的字符'O':
      - O不在need_dict中，跳过
      
      状态:
        window_dict: {'A':1, 'B':1, 'C':1}
        valid = 3
        满足条件，继续收缩
        
      当前窗口长度: 13-7=6
      6 == min_len=6，不更新最小窗口
      
      移除left=7的字符'D':
      - D不在need_dict中，跳过
      
      状态:
        window_dict: {'A':1, 'B':1, 'C':1}
        valid = 3
        满足条件，继续收缩
        
      当前窗口长度: 13-8=5
      5 < min_len=6，更新最小窗口: min_len=5, start=8
      
      移除left=8的字符'E':
      - E不在need_dict中，跳过
      
      状态:
        window_dict: {'A':1, 'B':1, 'C':1}
        valid = 3
        满足条件，继续收缩
        
      当前窗口长度: 13-9=4
      4 < min_len=5，更新最小窗口: min_len=4, start=9
      
      移除left=9的字符'B':
      - B在need_dict中
      - window_dict['B'] == need_dict['B'] (1==1) → valid=2
      - window_dict['B'] = 0
      
      状态:
        window_dict: {'A':1, 'B':0, 'C':1}
        valid = 2
        不满足条件，停止收缩
  • 最终结果
    1
    2
    最小窗口: s[9:9+4] = "BANC"
    返回结果: "BANC"

java版

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.util.HashMap;
import java.util.Map;

public class MinimumWindowSubstring {
    
    public static String minWindow(String s, String t) {
        /**
         * 找到s中涵盖t所有字符的最小子串
         * 
         * @param s 主字符串
         * @param t 目标字符串
         * @return 最小覆盖子串，如果不存在则返回空字符串
         */
        
        // 边界情况检查：如果s或t为空，或者s的长度小于t的长度，直接返回空字符串
        if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
            return "";
        }
        
        // 使用HashMap记录t中每个字符的出现次数
        Map<Character, Integer> needMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            needMap.put(c, needMap.getOrDefault(c, 0) + 1);
        }
        
        // 使用HashMap记录当前窗口中每个字符的出现次数
        Map<Character, Integer> windowMap = new HashMap<>();
        
        // 初始化左右指针、有效字符计数、最小窗口的起始位置和长度
        int left = 0;
        int right = 0;
        int valid = 0; // 记录窗口中满足needMap要求的字符数量
        int start = 0; // 最小窗口的起始位置
        int minLen = Integer.MAX_VALUE; // 最小窗口长度，初始化为最大整数
        
        // 滑动窗口，右指针遍历整个字符串s
        while (right < s.length()) {
            // 获取右指针指向的字符
            char c = s.charAt(right);
            // 右指针向右移动
            right++;
            
            // 如果当前字符在t中，则更新窗口计数
            if (needMap.containsKey(c)) {
                windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
                // 如果窗口中该字符的数量等于t中该字符的数量，则有效计数加1
                if (windowMap.get(c).equals(needMap.get(c))) {
                    valid++;
                }
            }
            
            // 当窗口中包含t的所有字符时，尝试收缩左指针
            while (valid == needMap.size()) {
                // 更新最小窗口
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }
                
                // 获取左指针指向的字符
                char d = s.charAt(left);
                // 左指针向右移动
                left++;
                
                // 如果移出的字符在t中，则更新窗口计数
                if (needMap.containsKey(d)) {
                    // 如果窗口中该字符的数量等于t中该字符的数量，则有效计数减1
                    if (windowMap.get(d).equals(needMap.get(d))) {
                        valid--;
                    }
                    windowMap.put(d, windowMap.get(d) - 1);
                }
            }
        }
        
        // 如果找到了最小窗口，返回对应的子串，否则返回空字符串
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
    
    // 测试代码
    public static void main(String[] args) {
        // 示例1
        String s1 = "ADOBECODEBANC";
        String t1 = "ABC";
        System.out.println("输入: s = \"" + s1 + "\", t = \"" + t1 + "\"");
        System.out.println("输出: \"" + minWindow(s1, t1) + "\""); // 输出: "BANC"
        
        // 示例2
        String s2 = "a";
        String t2 = "a";
        System.out.println("输入: s = \"" + s2 + "\", t = \"" + t2 + "\"");
        System.out.println("输出: \"" + minWindow(s2, t2) + "\""); // 输出: "a"
        
        // 示例3
        String s3 = "a";
        String t3 = "aa";
        System.out.println("输入: s = \"" + s3 + "\", t = \"" + t3 + "\"");
        System.out.println("输出: \"" + minWindow(s3, t3) + "\""); // 输出: ""
        
        // 额外测试用例
        String s4 = "aa";
        String t4 = "aa";
        System.out.println("输入: s = \"" + s4 + "\", t = \"" + t4 + "\"");
        System.out.println("输出: \"" + minWindow(s4, t4) + "\""); // 输出: "aa"
    }
}