最小覆盖子串

题目要求

编写一个算法，输入为两个字符串：s和t。目标是找到字符串s中的最小子串，该子串必须包含字符串t中的所有字符，并且如果t中的字符在s中有重复，那么在s的子串中找到的这个字符的数量也必须不少于在t中的数量。如果在s中找不到这样的子串，则返回一个空字符串""。题目还说明，如果存在满足条件的子串，那么这个子串是唯一的。

解题思路

这个问题可以通过滑动窗口的方法来解决。滑动窗口是一种常用的可以用来减少重复操作的方法，特别适合解决子字符串相关的问题。以下是解题的步骤：

初始化两个计数器：一个用于t的字符计数，另一个用于滑动窗口中的字符计数。
扩展窗口：从s的左端开始，向右移动窗口的右边界，直到窗口中包含了t中所有的字符，并且每个字符的数量也满足要求。
收缩窗口：一旦我们有了一个包含t中所有字符的窗口，我们就可以尝试移动窗口的左边界以缩小窗口，同时保持窗口中包含t中所有的字符。这一步是为了找到最小的满足条件的子串。
记录最小子串：在移动窗口的过程中，每次我们找到一个满足条件的子串，我们都检查它是否是到目前为止最小的一个，并记录其位置和长度。
重复步骤 2 和 3：继续移动窗口的右边界，重复步骤 2 和 3 的过程，直到右边界到达字符串s的末尾。
返回结果：根据记录的最小子串的位置和长度，返回最终的子串。如果没有找到满足条件的子串，则返回空字符串""。

在实现上述步骤时，需要注意的是如何高效地计数和比较字符。可以使用哈希表来存储字符的计数，这样可以在常数时间内完成字符的添加、删除和查找操作。此外，为了避免重复计算t中每个字符的数量，我们可以在算法开始之前预先计算好，并存储在哈希表中。

这个问题的关键在于如何高效地移动滑动窗口的两个边界，并在整个过程中维护好字符的计数。通过不断地调整窗口的大小，直到找到最小的包含t中所有字符的子串，我们就可以得到问题的答案。

Golang 版本

package main

import (
	"fmt"
	"math"
)

func minWindow(s string, t string) string {
	if len(s) == 0 || len(t) == 0 {
		return ""
	}

	// 记录t中每个字符出现的次数
	tFreq := make(map[byte]int)
	for i := 0; i < len(t); i++ {
		tFreq[t[i]]++
	}

	// 记录当前窗口中每个字符出现的次数
	windowFreq := make(map[byte]int)

	// 滑动窗口的左右边界
	left, right := 0, 0

	// 记录已经找到的字符个数
	found := 0

	// 记录最小覆盖子串的起始索引及长度
	minLeft, minSize := 0, math.MaxInt32

	for right < len(s) {
		// 如果右边的字符是t中的字符，则加入窗口
		if _, ok := tFreq[s[right]]; ok {
			windowFreq[s[right]]++
			if windowFreq[s[right]] <= tFreq[s[right]] {
				found++
			}
		}

		// 当窗口已经包含了t中所有字符
		for found == len(t) {
			// 更新最小覆盖子串
			if right-left+1 < minSize {
				minLeft = left
				minSize = right - left + 1
			}

			// 尝试缩小窗口
			if _, ok := tFreq[s[left]]; ok {
				windowFreq[s[left]]--
				if windowFreq[s[left]] < tFreq[s[left]] {
					found--
				}
			}
			left++
		}

		right++
	}

	if minSize == math.MaxInt32 {
		return ""
	}

	return s[minLeft : minLeft+minSize]
}

func main() {
	s := "ADOBECODEBANC"
	t := "ABC"
	fmt.Println("Minimum window substring is:", minWindow(s, t))
}

这段代码实现了上述的滑动窗口算法，用于寻找字符串s中包含字符串t所有字符的最小子串。如果存在这样的子串，它将被打印出来；如果不存在，将打印出一个空字符串。

C++版本

#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>

std::string minWindow(std::string s, std::string t) {
    if (s.empty() || t.empty()) {
        return "";
    }

    std::unordered_map<char, int> tFreq;
    for (char c : t) {
        ++tFreq[c];
    }

    std::unordered_map<char, int> windowFreq;
    int left = 0, right = 0;
    int required = tFreq.size();
    int formed = 0;
    int minLen = INT_MAX, minStart = 0;

    while (right < s.length()) {
        char c = s[right];
        if (tFreq.find(c) != tFreq.end()) {
            windowFreq[c]++;
            if (windowFreq[c] == tFreq[c]) {
                formed++;
            }
        }

        while (left <= right && formed == required) {
            c = s[left];
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }

            if (tFreq.find(c) != tFreq.end()) {
                windowFreq[c]--;
                if (windowFreq[c] < tFreq[c]) {
                    formed--;
                }
            }

            left++;
        }

        right++;
    }

    return minLen == INT_MAX ? "" : s.substr(minStart, minLen);
}

int main() {
    std::string s = "ADOBECODEBANC";
    std::string t = "ABC";
    std::string minSubstr = minWindow(s, t);
    std::cout << "Minimum window substring is: " << minSubstr << std::endl;
    return 0;
}

这段 C++代码实现了寻找字符串s中包含字符串t所有字符的最小子串的功能。如果找到了这样的子串，它会被输出；如果没有找到，输出将是一个空字符串。

Python 版本

from collections import Counter

def min_window(s, t):
    if not t or not s:
        return ""

    dict_t = Counter(t)
    required = len(dict_t)

    l, r = 0, 0
    formed = 0
    window_counts = {}

    ans = float("inf"), None, None

    while r < len(s):
        character = s[r]
        window_counts[character] = window_counts.get(character, 0) + 1

        if character in dict_t and window_counts[character] == dict_t[character]:
            formed += 1

        while l <= r and formed == required:
            character = s[l]

            if r - l + 1 < ans[0]:
                ans = (r - l + 1, l, r)

            window_counts[character] -= 1
            if character in dict_t and window_counts[character] < dict_t[character]:
                formed -= 1

            l += 1

        r += 1

    return "" if ans[0] == float("inf") else s[ans[1]:ans[2] + 1]

# Example usage:
s = "ADOBECODEBANC"
t = "ABC"
print(min_window(s, t))

这段 Python 代码实现了寻找字符串s中包含字符串t所有字符的最小子串的功能。如果找到了这样的子串，它会被打印出来；如果没有找到，打印将是一个空字符串。

Java 版本

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public static String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length() || s.length() == 0) {
            return "";
        }

        Map<Character, Integer> dictT = new HashMap<Character, Integer>();
        for (int i = 0; i < t.length(); i++) {
            dictT.put(t.charAt(i), dictT.getOrDefault(t.charAt(i), 0) + 1);
        }

        int required = dictT.size();
        int l = 0, r = 0;
        int formed = 0;

        Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();
        int[] ans = {-1, 0, 0};

        while (r < s.length()) {
            char c = s.charAt(r);
            windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);

            if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
                formed++;
            }

            while (l <= r && formed == required) {
                c = s.charAt(l);
                if (ans[0] == -1 || r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }

                windowCounts.put(c, windowCounts.get(c) - 1);
                if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
                    formed--;
                }

                l++;
            }

            r++;
        }

        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println("Minimum window substring is: " + minWindow(s, t));
    }
}

这段 Java 代码实现了寻找字符串s中包含字符串t所有字符的最小子串的功能。如果找到了这样的子串，它会被输出；如果没有找到，输出将是一个空字符串。

Rust 版本

use std::collections::HashMap;

fn min_window(s: String, t: String) -> String {
    let mut t_freq = HashMap::new();
    for c in t.chars() {
        *t_freq.entry(c).or_insert(0) += 1;
    }

    let (mut start, mut min_len, mut left, mut right, mut formed) = (0, usize::MAX, 0, 0, 0);
    let mut window_freq = HashMap::new();
    let required = t_freq.len();

    while right < s.len() {
        let c = s.chars().nth(right).unwrap();
        *window_freq.entry(c).or_insert(0) += 1;

        if t_freq.contains_key(&c) && window_freq[&c] == t_freq[&c] {
            formed += 1;
        }

        while left <= right && formed == required {
            let c = s.chars().nth(left).unwrap();

            if right - left + 1 < min_len {
                min_len = right - left + 1;
                start = left;
            }

            window_freq.entry(c).and_modify(|e| *e -= 1);
            if t_freq.contains_key(&c) && window_freq[&c] < t_freq[&c] {
                formed -= 1;
            }

            left += 1;
        }
        right += 1;
    }

    if min_len == usize::MAX {
        "".to_string()
    } else {
        s[start..start + min_len].to_string()
    }
}

fn main() {
    let s = String::from("ADOBECODEBANC");
    let t = String::from("ABC");
    println!("Minimum window substring is: {}", min_window(s, t));
}

这段 Rust 代码实现了寻找字符串s中包含字符串t所有字符的最小子串的功能。如果找到了这样的子串，它会被输出；如果没有找到，输出将是一个空字符串。

总结

上述问题的解法遵循了一种称为“滑动窗口”的算法策略。无论是在 Python、C++、Java 还是 Rust 版本的代码中，核心思想都是相同的，即通过维护一个窗口来寻找包含目标字符串t所有字符的最小子串。以下是解法的关键步骤：

初始化两个指针：一个左指针（left或l）和一个右指针（right或r），分别代表窗口的开始和结束位置。
字符频率映射：使用哈希表（或字典）来记录字符串t中每个字符的频率。
扩展右指针：移动右指针以扩大窗口，直到窗口包含了t中所有的字符。
收缩左指针：一旦找到了一个有效的窗口，即包含了t中所有字符的子串，就开始移动左指针以缩小窗口，同时更新最小子串的长度和起始位置。这一步是为了找到不包含额外字符的最小长度子串。
更新结果：在整个过程中，记录并更新满足条件的最小子串的长度和起始位置。
返回结果：根据记录的最小长度和起始位置，返回最终的最小子串。如果没有找到满足条件的子串，则返回空字符串。

这个算法的时间复杂度通常是 O(n)，其中 n 是字符串s的长度，因为每个字符最多被访问两次（一次是右指针向右移动，一次是左指针向右移动）。空间复杂度取决于字符串t的长度，因为需要存储t中每个字符的频率。

hot-100