给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出："BANC"
示例 2：
输入：s = “a”, t = “a”
输出："a"
提示：
1 <= s.length, t.length <= 105
s 和 t 由英文字母组成
题意：在字符串s中找到能覆盖字符串t的最小子串。
思路：滑动窗口。
正确代码：
class Solution { public String minWindow(String s, String t) { if(s.length()<t.length()) return ""; HashMap<Character,Integer> needs = new HashMap<>(); HashMap<Character,Integer> window = new HashMap<>(); //统计每个字符出现了多少次，以key-value的形式记录 for (int i = 0; i < t.length(); i++) { needs.put(t.charAt(i),needs.getOrDefault(t.charAt(i),0)+1); } //System.out.println("needs.size(): "+needs.size()); int left =0,right=0; int valid =0; //记录多少个字符串符合了条件,valid==needs.size() 就证明全部包含了 //start : 最小符合子串的起始位置 len:最小符合子串的长度 int start =0,len =Integer.MAX_VALUE; while(right<s.length()){ char c1= s.charAt(right); if(needs.containsKey(c1)){ window.put(c1,window.getOrDefault(c1,0)+1); if(window.get(c1).equals(needs.get(c1))){ valid++; } } right++; //判断是否需要收缩 while(valid==needs.size()){ if(right-left<len){ len = right-left; start=left; } char c2 =s.charAt(left); left++; if(needs.containsKey(c2)){ window.put(c2,window.put(c2,0)-1); if(window.get(c2)<needs.get(c2)){ valid--; } } } } String a = Integer.toString(len); return a.equals(Integer.toString(Integer.MAX_VALUE) )? "" : s.substring(start, start + len); } }
完整代码（含测试代码）：
package com.Keafmd.February.day11; import java.util.HashMap; /** * Keafmd * * @ClassName: MinimumWindowSubstring * @Description: 最小覆盖子串 https://leetcode-cn.com/problems/minimum-window-substring/ * @author: 牛哄哄的柯南 * @Date: 2021-03-11 9:08 * @Blog: https://keafmd.blog.csdn.net/ */ public class MinimumWindowSubstring { public static void main(String[] args) { String s = "ADOBECODEBANC", t = "ABC"; //String s = "a", t = "aa"; //String s = "a", t = "b"; Solution03111 solution03111 = new Solution03111(); String re = solution03111.minWindow(s,t); System.out.println(re); } } class Solution03111 { public String minWindow(String s, String t) { if(s.length()<t.length()) return ""; HashMap<Character,Integer> needs = new HashMap<>(); HashMap<Character,Integer> window = new HashMap<>(); //统计每个字符出现了多少次，以key-value的形式记录 for (int i = 0; i < t.length(); i++) { needs.put(t.charAt(i),needs.getOrDefault(t.charAt(i),0)+1); } //System.out.println("needs.size(): "+needs.size()); int left =0,right=0; int valid =0; //记录多少个字符串符合了条件,valid==needs.size() 就证明全部包含了 //start : 最小符合子串的起始位置 len:最小符合子串的长度 int start =0,len =Integer.MAX_VALUE; while(right<s.length()){ char c1= s.charAt(right); if(needs.containsKey(c1)){ window.put(c1,window.getOrDefault(c1,0)+1); if(window.get(c1).equals(needs.get(c1))){ valid++; } } right++; //判断是否需要收缩 while(valid==needs.size()){ if(right-left<len){ len = right-left; start=left; } char c2 =s.charAt(left); left++; if(needs.containsKey(c2)){ window.put(c2,window.put(c2,0)-1); if(window.get(c2)<needs.get(c2)){ valid--; } } } } String a = Integer.toString(len); return a.equals(Integer.toString(Integer.MAX_VALUE) )? "" : s.substring(start, start + len); } }
输出结果：
BANC Process finished with exit code 0
