题解 | #最小覆盖子串#

最小覆盖子串

https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String s, String t) {
        // write code here
          if (s == null || t == null || s.length() == 0 || t.length() == 0 || t.length() > s.length()) {
            return "";
        }

        // 记录t中每个字符出现的次数
        Map<Character, Integer> tFreq = new HashMap<>();
        for (char c : t.toCharArray()) {
            tFreq.put(c, tFreq.getOrDefault(c, 0) + 1);
        }

        int left = 0;  // 窗口的左边界
        int right = 0;  // 窗口的右边界
        int formed = 0;  // 记录窗口中包含t中字符的个数
        int required = tFreq.size();  // t中不同字符的个数
        Map<Character, Integer> windowFreq = new HashMap<>();  // 记录窗口中每个字符出现的次数

        int minLen = Integer.MAX_VALUE;  // 最小符合条件的子串的长度
        int minStart = -1;  // 最小符合条件的子串的起始位置

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

            if (tFreq.containsKey(c) && windowFreq.get(c).intValue() == tFreq.get(c).intValue()) {
                formed++;
            }

            // 缩小窗口的范围，直到不再满足条件
            while (left <= right && formed == required) {
                c = s.charAt(left);

                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minStart = left;
                }

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

                left++;
            }

            right++;
        }

        if (minStart == -1) {
            return "";
        }

        return s.substring(minStart, minStart + minLen);
    }
}

这道题可以使用滑动窗口的方法来解决。定义两个指针left和right来表示窗口的左边界和右边界。

首先，我们先使用一个哈希表来记录字符串t中每个字符出现的次数，以便后面判断窗口中是否包含了t中的所有字符。

然后，使用双指针left和right来遍历字符串s。在每一步迭代中，先将right向右移动，直到窗口中包含了字符串t中的所有字符。

然后，再将left向右移动，缩小窗口的范围，找到最短的符合条件的子串。

最后，返回符合条件的子串。如果找不到，返回空字符串。

首先，我们创建一个哈希表tFreq来记录字符串t中每个字符出现的次数。然后，我们定义left和right作为窗口的左边界和右边界。

接下来，我们使用right向右移动，直到窗口中包含了字符串t中的所有字符。然后，我们使用left向右移动，缩小窗口的范围，找到最短的符合条件的子串。

在每一步迭代中，我们将每个位置的字符加入窗口中，并更新windowFreq的计数。如果该字符也出现在t中，并且窗口中该字符的数量等于tFreq中该字符的数量，我们将formed增加1。

当窗口中包含了t中的所有字符时，我们开始缩小窗口的范围。我们将left向右移动，剔除窗口的左边界字符，并根据需要更新formed的值。

当窗口不再满足条件时，我们再次将right向右移动，重新扩展窗口。

最后，我们得到了最短的符合条件的子串，我们可以根据minStart和minLen来截取字符串s，返回结果。

时间复杂度为O(n)，其中n是字符串s的长度。空间复杂度为O(n)，用于存储哈希表和窗口内字符的计数。