解答 #

class Solution {
    int[] countS;
    int[] countT;
    public boolean check(){
        for(int i=0;i<52+6;i++){
            if(countS[i]<countT[i]) return false;
        }
        return true;
    }
    public String minWindow(String s, String t) {
        countS=new int[52+6];
        countT=new int[52+6];
        int sLen=s.length();
        int tLen=t.length();
        char[] tArr=t.toCharArray();
        char[] sArr=s.toCharArray();
        for(char ch:tArr){
            countT[ch-'A']++;
        }
        int tail=0;
        
        int len = Integer.MAX_VALUE;
        int resL=-1;
        int resR=-1;
        for(int i=0;i<sLen;i++){
            countS[sArr[i]-'A']++;
            while(check()&&tail<=i){
                if(i-tail+1<len){
                    len=i-tail+1;
                    resL=tail;
                    resR=i;
                }
                
                countS[sArr[tail]-'A']--;
                tail++;
            }
        }
        return resL== -1 ? "" : s.substring(resL, resR+1);
    }
}

class Solution {
    public String minWindow(String s, String t) {
        int[] countS=new int[52+6];
        int[] count=new int[52+6];
        int sLen=s.length();
        int tLen=t.length();
        char[] tArr=t.toCharArray();
        char[] sArr=s.toCharArray();
        int diff=0;
        for(char ch:tArr){
            count[ch-'A']++;
            if(count[ch-'A']==1) diff++;
        }
        int tail=0;
        
        int len = Integer.MAX_VALUE;
        int resL=-1;
        int resR=-1;
        for(int i=0;i<sLen;i++){
            count[sArr[i]-'A']--;
            if(count[sArr[i]-'A']==0) diff--;
            while(diff==0&&tail<=i){
                if(i-tail+1<len){
                    len=i-tail+1;
                    resL=tail;
                    resR=i;
                }
                count[sArr[tail]-'A']++;
                if(count[sArr[tail]-'A']==1) diff++;
                tail++;
            }
        }
        return resL== -1 ? "" : s.substring(resL, resR+1);
    }
}

class Solution {
    public String minWindow(String s, String t) {
        // 数组大小保持原来的 52+6，这里假设 t 中字符均在 'A'~'z' 范围内
        int[] count = new int[58];  
        int diff = 0;
        // 预处理 t，将 t 中的每个字符的计数设为负数，负数的绝对值表示还需要多少个
        for (char ch : t.toCharArray()) {
            if (count[ch - 'A'] == 0) {
                diff++; // diff 表示还需要满足多少种不同的字符
            }
            count[ch - 'A']--;
        }
        
        int left = 0;
        int minLen = Integer.MAX_VALUE;
        int resL = -1;
        
        // 滑动窗口：right 指针表示窗口右边界
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            // 加入当前字符到窗口，计数加 1
            count[c - 'A']++;
            // 当某字符的计数从负数变为 0，说明该字符已经满足 t 的要求
            if (count[c - 'A'] == 0) {
                diff--;
            }
            
            // 当 diff 为 0 时，说明当前窗口已经包含 t 中所有字符
            while (diff == 0 && left <= right) {
                // 尝试更新最小覆盖子串
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    resL = left;
                }
                // 移除窗口左侧字符
                char leftChar = s.charAt(left);
                count[leftChar - 'A']--;  // 移除时减 1
                // 如果移除后该字符的计数变为 -1，说明 t 中该字符又不满足了
                if (count[leftChar - 'A'] == -1) {
                    diff++;
                }
                left++;
            }
        }
        return resL == -1 ? "" : s.substring(resL, resL + minLen);
    }
}