NC28 最小覆盖子串

描述

给出两个字符串 s 和 t, 要求在 s 中找出最短的包含 t 中所有字符的连续子串。

示例1

输入：XDOYEZODEYXNZ，XYZ

输出：YXNZ

示例2

输入：abcAbA，AA

输出：AbA

代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String input = in.nextLine();
        String[] parts = input.split(",");

        String s = parts[0];
        String t = parts[1];

        System.out.println(minWindow(s, t));
    }

    public static String minWindow(String s, String t) {
        // 如果s或t为空，或者s的长度小于t的长度，则返回空字符串
        if (s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
            return "";
        }

        // 初始化两个数组，用于存储t中字符的计数和s中窗口内字符的计数
        int[] tCount = new int[256]; // ASCII字符集大小为256
        int[] sCount = new int[256]; 

        // 初始化需要的字符数量，即t的长度
        int required = t.length(); // 需要的字符数量
        int formed = 0; // 已经形成的字符数量

        // 遍历t中的每个字符，并在tCount数组中增加对应的计数
        for (char c : t.toCharArray()) {
            tCount[c]++;
        }

        // 初始化窗口的左右边界
        int l = 0, r = 0;
        // 初始化最小窗口的长度和起始位置
        int minLen = Integer.MAX_VALUE, minStart = 0;
        // 初始化窗口内满足条件的字符数量
        int h = 0; // 窗口内满足条件的字符数量

        // 遍历字符串s
        while (r < s.length()) {
            // 取出当前字符
            char c = s.charAt(r);
            // 在sCount数组中增加当前字符的计数
            sCount[c]++;

            // 如果当前字符的计数小于或等于tCount中的计数，则增加formed的值
            if (sCount[c] <= tCount[c]) {
                formed++;
            }

            // 当窗口内所有字符都满足条件时，尝试缩小窗口
            while (l <= r && formed == required) {
                // 如果当前窗口的长度小于之前找到的最小窗口，则更新最小窗口的长度和起始位置
                if (minLen > r - l + 1) {
                    minLen = r - l + 1;
                    minStart = l;
                }

                // 缩小窗口，从左侧移除字符，并减少sCount中的计数
                char d = s.charAt(l);
                sCount[d]--;
                // 如果移除后字符的计数小于tCount中的计数，则减少formed的值
                if (sCount[d] < tCount[d]) {
                    formed--;
                }
                l++;
            }
            // 扩大窗口，向右移动
            r++;
        }

        // 如果找到了最小窗口，则返回该窗口的子字符串，否则返回空字符串
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }
}