解题思路

本题是经典的“最小覆盖子串”问题，适用 滑动窗口 + 计数 的思想。核心做法如下：

1. 用一个长度为 128 的整型数组 need 统计字符串 t 中每个字符需要的数量（只含英文字母，用 ASCII 足够）。
2. 维护双指针 [left, right] 表示当前窗口，并维护变量 missing 表示还缺多少个字符（按出现次数计），初始为 |t|。
3. 向右移动 right 扩张窗口：将 s[right] 对应的 need 计数减一；若减完后该字符的 need 仍 ≥ 0，说明它满足了 t 的部分需求，missing--。
4. 当 missing == 0 时，说明当前窗口已经覆盖了 t 的所有字符，此时尝试收缩左端 left，在仍满足覆盖条件下尽量缩短长度，并记录当前最短答案。一旦收缩到去掉 s[left] 会使 need[s[left]] > 0，表明覆盖被破坏，停止收缩并继续扩张右端。
5. 扫描结束后，若记录过答案则输出最短子串，否则输出空串。

复杂度分析

• 时间复杂度：每个字符至多被左右指针各访问一次，O(|s| + |t|)。
• 空间复杂度：计数数组大小与字符集有关（固定 128），O(1)。

代码实现

Python

import sys

# 功能函数：返回最短覆盖子串
def min_window(s: str, t: str) -> str:
    # 边界处理
    if not s or not t or len(t) > len(s):
        return ""

    # 统计 t 中每个字符需要的数量
    need = [0] * 128
    for ch in t:
        need[ord(ch)] += 1

    missing = len(t)         # 还缺的字符总数（按次数计）
    left = 0                 # 左指针
    best_len = float('inf')  # 记录最优长度
    best_l = 0               # 记录最优左端点

    # 右指针扩张窗口
    for right, ch in enumerate(s):
        c = ord(ch)
        need[c] -= 1
        if need[c] >= 0:     # 该字符确实用于弥补缺口
            missing -= 1

        # 当前窗口已覆盖 t，尝试左缩
        while missing == 0:
            # 更新最优答案
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_l = left

            # 左端右移，若破坏覆盖则停止
            cl = ord(s[left])
            need[cl] += 1
            if need[cl] > 0:  # 去掉了一个必须的字符
                missing += 1
            left += 1

    return "" if best_len == float('inf') else s[best_l:best_l + best_len]

def main():
    data = sys.stdin.read().splitlines()
    if not data:
        return
    s = data[0]
    t = data[1] if len(data) > 1 else ""
    ans = min_window(s, t)
    # 题意要求输出空字符串时不带引号，即输出空行
    print(ans)

if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    // 功能函数：返回最短覆盖子串
    public static String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0 || t.length() > s.length()) {
            return "";
        }

        int[] need = new int[128]; // 统计 t 中字符需求
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }

        int missing = t.length(); // 还缺的字符总数
        int left = 0;
        int bestLen = Integer.MAX_VALUE;
        int bestL = 0;

        // 右指针扩张
        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            need[ch]--;
            if (need[ch] >= 0) { // 有效弥补
                missing--;
            }

            // 已覆盖，尝试左缩
            while (missing == 0) {
                if (right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestL = left;
                }
                char cl = s.charAt(left);
                need[cl]++;
                if (need[cl] > 0) { // 去掉必须字符，破坏覆盖
                    missing++;
                }
                left++;
            }
        }

        if (bestLen == Integer.MAX_VALUE) return "";
        return s.substring(bestL, bestL + bestLen);
    }

    public static void main(String[] args) throws IOException {
        // 根据数据范围使用 BufferedReader 读取两行
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String t = br.readLine();
        if (s == null) s = "";
        if (t == null) t = "";
        String ans = minWindow(s, t);
        System.out.print(ans); // 若为空则输出空行（不带引号）
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

// 功能函数：返回最短覆盖子串
string minWindow(const string& s, const string& t) {
    if (s.empty() || t.empty() || t.size() > s.size()) return "";

    vector<int> need(128, 0);      // 统计 t 中字符需求
    for (char ch : t) need[(unsigned char)ch]++;

    int missing = (int)t.size();    // 还缺的字符总数
    int left = 0;
    int bestLen = INT_MAX;
    int bestL = 0;

    // 右指针扩张窗口
    for (int right = 0; right < (int)s.size(); ++right) {
        unsigned char c = (unsigned char)s[right];
        need[c]--;
        if (need[c] >= 0) {         // 有效弥补
            missing--;
        }

        // 当前窗口已覆盖，尝试左缩
        while (missing == 0) {
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestL = left;
            }
            unsigned char cl = (unsigned char)s[left];
            need[cl]++;
            if (need[cl] > 0) {     // 去掉必须字符，破坏覆盖
                missing++;
            }
            left++;
        }
    }

    if (bestLen == INT_MAX) return "";
    return s.substr(bestL, bestLen);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, t;
    if (!getline(cin, s)) s = "";
    if (!getline(cin, t)) t = "";

    string ans = minWindow(s, t);
    cout << ans; // 若为空则输出空行（不带引号）
    return 0;
}

题目内容

给定字符串 s 与字符串 t，请在 s 中找出包含 t 中所有字符(含出现次数) 的最短子串并输出该子串。 若 s 中不存在这样的子串，输出空字符串 ""（不带引号）。

注：对 t 中重复字符，子串中对应字符的数量必须不少于 t 中该字符的数量。若存在解，保证答案唯一。

输入描述

• 第一行：字符串 s
• 第二行：字符串 t

输出描述

• 一行：最短覆盖子串；若不存在则输出空字符串 ""，不包含引号。

样例一

输入：

ADOBECODEBANC
ABC

输出：

BANC

样例二

输入：

a
a

输出：

a

样例三

输入：

a
aa

输出：

数据范围

• $1 ≤ |s|, |t| ≤ 10^5$
• s与t由英文字母组成