Leetcode 76-最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

题解转载自图解Leetcode

class Solution {
    public String minWindow(String s, String t) {
        int[] arrayT = new int[52];
        int[] arrayS = new int[52];

        int validAllCount = 0;
        // 对目标数据计数
        for (char c : t.toCharArray()) {
            arrayT[getIndex(c)]++;
            if (arrayT[getIndex(c)] == 1) {
                validAllCount++;
            }
        }
        // 初始化左右指针
        int l = 0, r = 0;

        // 初始化最小的字符串长度及开始索引
        int minLen = Integer.MAX_VALUE;
        int start = 0;

        // 校验值初始化,当valid与
        int valid = 0;

        while (r < s.length()) {
            char cur = s.charAt(r);
            r++;
            // 逻辑代码,窗口内数据更新
            int index = getIndex(cur);
            if (arrayT[index] > 0) {
                arrayS[index]++;
                if (arrayT[index] == arrayS[index]) {
                    valid++;
                }
            }

            // 满足条件收缩左指针
            while (valid == validAllCount) {
                // 存储满足条件的数据
                if (r - l < minLen) {
                    start = l;
                    minLen = r - l;
                }
                // 获取左指针即将移除的元素
                char curDel = s.charAt(l);
                l++;
                // 逻辑代码,窗口内数据更新
                int indexDel = getIndex(curDel);
                if (arrayS[indexDel] > 0) {
                    if (arrayT[indexDel] == arrayS[indexDel]) {
                        valid--;
                    }
                    arrayS[indexDel]--;
                }
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }

    private int getIndex(char c) {
        return c - 'a' >= 0 ? c - 'a' : c - 'A' + 26;
    }
}