给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
- 如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释:
t 中两个字符 'a' 均应包含在 s 的子串中。因此没有符合条件的子字符串，返回空字符串。
解答
一共写了三版代码，其中前两版本代码均超时，第三版本代码时间复杂度为O(n)没有超时
class Solution {
public String minWindow(String s, String t) {
// 记录t中字符与s中匹配的元素下标
int[] indexFromS = new int[t.length()];
for (int i = 0; i < t.length(); i++) {
indexFromS[i] = -1;
}
StringBuilder res = new StringBuilder();
boolean ifSkip = false;
for (int l = 0, r = 0, restCharCount = t.length(); r < s.length() && l <= r; ) {
// 如果当前r所指s字符存在于t中，更新charCounter与restCharCount状态
if (t.indexOf(s.charAt(r)) != -1 && !ifSkip) {
char c = s.charAt(r);
int minIndexT = 0;
for (int start = t.indexOf(c, 0), minIndexS = s.length();
start < t.length() && start != -1; start = t.indexOf(c, start+1)) {
if (indexFromS[start] < minIndexS && indexFromS[start] >= 0) {
minIndexS = indexFromS[start];
minIndexT = start;
} else if (indexFromS[start] == -1) {
minIndexT = start;
restCharCount--;
break;
}
}
indexFromS[minIndexT] = r;
}
// 如果restCharCount == 0，说明t中字符已全部出现。此时更新res，l，r，restCharCount，indexFromS
if (restCharCount == 0) {
if (res.length() == 0) { res.append(s, l, r+1); }
int occurIndex = -1;
// 确定当前l指针所指元素，是否被t中某字符使用
for (int i = 0; i < indexFromS.length; i++) {
if (indexFromS[i] == l) {
occurIndex = i;
break;
}
}
if (occurIndex != -1) {
// 当l指针处的字符在t中被使用，此时的l-r子串是局部最优解
if (r-l+1 < res.length()) {
res.replace(0, res.length(), s.substring(l, r+1));
}
indexFromS[occurIndex] = -1;
l++;
restCharCount++;
} else {
// l指针处的字符不存在于t中，直接右移l指针
l++;
ifSkip = true;
continue;
}
}
r++;
ifSkip = false;
}
return res.toString();
}
}
第二版代码
public class ShowPos {
public char c;
public int showPos;
public ShowPos(char c, int showPos) {
this.c = c;
this.showPos = showPos;
}
}
class Solution {
public String minWindow(String s, String t) {
if (s.length() < t.length()) return "";
int left = 0, right = 0; // 用于记录每次更新的子串起始位置下标
Map<Character, Integer> showTimesMap = new HashMap<>(); // 记录出现在t中的字符与其数量。
// 在遍历s以添加字符到子串的过程中会动态维护，
// 用于存储子串中缺失的字符与其数量
char c;
for (int i = 0; i < t.length(); i++) {
showTimesMap.put(c = t.charAt(i), showTimesMap.containsKey(c) ? showTimesMap.get(c)+1 : 1);
}
LinkedList<ShowPos> showPosQueue = new LinkedList<>();
String minSubStr = "1"+s;
int index = 0;
while (index < s.length()) {
if (showTimesMap.containsKey(c = s.charAt(index))) {
// s当前遍历的字符存在于t，
if (showTimesMap.get(c) > 0) {
// 当前子串中该字符出现次数少于在t中出现次数
showPosQueue.add(new ShowPos(c, index));
showTimesMap.put(c, showTimesMap.get(c)-1);
} else {
ShowPos newNode;
for (int i = 0; i < showPosQueue.size(); i++) {
if (showPosQueue.get(i).c == c) {
newNode = new ShowPos(c, index);
showPosQueue.remove(i);
showPosQueue.add(newNode);
break;
}
}
}
if (showPosQueue.size() == t.length() && minSubStr.length()-1 > index-showPosQueue.peek().showPos) {
// 当子串包含t中所有字符，且当前子串比历史最小子串更短时，更新最小子串
minSubStr = s.substring(showPosQueue.peek().showPos, index+1);
}
}
index++;
}
return minSubStr.equals("1"+s) ? "" : minSubStr;
}
}
第三版本代码
class Solution {
public String minWindow(String s, String t) {
if (t == null || s.length() < t.length() || t.length() == 0) return "";
Map<Character, Integer> showTimesMap = new HashMap<>(); // 记录出现在t中的字符与其数量。
// 在遍历s以添加字符到子串的过程中会动态维护，
// 用于存储子串中缺失的字符与其数量
Map<Character, LinkedList<Integer>> showPosMap = new HashMap<>(); // 对t中所有字符，记录在s中出现的位置
char c;
for (int i = 0; i < t.length(); i++) {
showTimesMap.put(c = t.charAt(i), showTimesMap.containsKey(c) ? showTimesMap.get(c)+1 : 1);
if (!showPosMap.containsKey(c)) showPosMap.put(c, new LinkedList<>());
}
boolean[] isShowChar = new boolean[s.length()];
for (int i = 0; i < s.length(); i++) {
if (showPosMap.containsKey((c = s.charAt(i)))) {
showPosMap.get(c).add(i);
isShowChar[i] = true;
}
}
String minSubStr = "1"+s;
int index = 0, leftCharNum = t.length(), leftPos = -1;
while (index < s.length()) {
if (showTimesMap.containsKey(c = s.charAt(index))) {
// s当前遍历的字符存在于t
leftPos = leftPos==-1 ? index : leftPos;
if (showTimesMap.get(c) > 0) {
// 当前子串中该字符出现次数少于在t中出现次数
showTimesMap.put(c, showTimesMap.get(c)-1);
leftCharNum--;
} else {
if (c == s.charAt(leftPos))
// 如果新加入到子串的字符和当前子串开头的字符相同
for (int i = leftPos+1; i < s.length(); i++)
if (isShowChar[i]) {
leftPos = i;
break;
}
isShowChar[showPosMap.get(c).getFirst()] = false;
showPosMap.get(c).removeFirst();
}
if (leftCharNum == 0 && minSubStr.length() > index-leftPos+1)
// 当子串包含t中所有字符，且当前子串比历史最小子串更短时，更新最小子串
minSubStr = s.substring(leftPos, index+1);
}
index++;
}
return minSubStr.equals("1"+s) ? "" : minSubStr;
}
}
