76. 最小覆盖子串(leetcode)

https://leetcode.cn/problems/minimum-window-substring/description/

难点在于解决字符出现次数的计算以及如何理解[涵盖],如何判断是否涵盖

class Solution {public String minWindow(String S, String t) {// 涵盖:s子串中每个字母出现的次数都大于等于t每个字母出现的次数String res="";int resLeft=-1;int resRight=S.length();char[] s=S.toCharArray();int[] cntS = new int[128]; // s 子串字母的出现次数int[] cntT = new int[128]; // t 中字母的出现次数for(char c:t.toCharArray())cntT[c]++;for(int i=0,j=0;i<s.length;i++){cntS[s[i]]++; // 新加入字符while(check(cntS,cntT)) // 判断是否涵盖{if(resRight-resLeft > i-j) // 更新答案{resRight=i;resLeft=j;}// 移动左指针缩小cntS[s[j]]--;j++;}}return resLeft < 0 ? "" : S.substring(resLeft,resRight+1);}// 传入s的子串,和t,判断是否涵盖boolean check(int[] cntS,int[] cntT){for(int i='A';i<='z';i++)if(cntS[i] < cntT[i]) return false;// for(int i='a';i<='z';i++)//     if(cntS[i] < cntT[i]) return false;return true;}   
}