求字符串s涵盖字符t中所有字符的最小子串长度

提示：这个不再是动态规划了，见过一次就要小新，当时我设计范围上的尝试失败了，实际上涵盖字符串这种，就是欠债策略
左神的欠债策略，能解决很多问题
窗口内的字符统计，数组表示哈希表，非常有趣的。

文章目录

• 求字符串s涵盖字符t中所有字符的最小子串长度
• • @[TOC](文章目录)
• 题目
• 一、审题
• 二、解题
• 总结

题目

求字符串s涵盖字符t中所有字符的最小子串长度
字符串t中如有重复的字符，那至少s要包含t中那么多字符
如果找不到一个s的子串涵盖了t的所有字符，那就返回0；

一、审题

示例：上面说的重复那种，案例如：
s=aksa，t=sk，最少2长度的子串，才能涵盖t
s=akskkks，t=ssk，最少5长度的子串，才能涵盖t

二、解题

这个题，就是欠账策略来还
利用窗口L–R内的还账情况，来更新最短的子串长
我们的宏观调度，
是判断每一个i为开头的达标的子串长度是否可以更新为最短的子串长度；

那么如何还债呢？

拿到t，咱们用一个哈希表统计，t中每种字符，有几个词频，相当于，一会你达标的窗口，至少要全部涵盖这么多词频，也就是map记录着窗口需要还的债。
比如：

真实在代码中，咱们最好别用哈希表，因为哈希表速度慢，虽然o(1)操作复杂度，司机上操作字符串的话，还是挺慢的
这里我们遇到的都是a–z的字符，ASCII码a=97，A=65，故就这么几个有限的字符，要统计词频根本不需要哈希表
直接用256数组长的数组，统计词频即可：

好，有了欠债表，咱们就可以用滑动窗口来还债了；
（1）最开始，咱们的窗口长为0，L=0,R=0,用[L–R)来表示一个窗口，【左闭右开】，代表一个字符都没有纳入；
（2）然后开始扩窗，每扩一个窗R++，词频表中对应s[R]字符的数量–，代表还了一个字符
t的长度为all，代表一共需要还t这么多字符【想要全部涵盖的话】
（3）第一次，扩到all=0时，说明此时刚刚好达标了，还完了
但是你瞅瞅，是不是s[L]字符，在map词频表中的词频小于0
小于0意味着什么？意味着，窗口内多还给t了，于是词频竟然变负了，这是不行的
那L++ ，保证把还多了的吐出来，这样子串才变短
直到吐完，s[L]这个字符的词频在map中为0，说明此时all=0，达标，而且没有多还，必然是一个最短的子串长，更新min

（4）人为将L++一次，换别的L开头，看看还有没有可能找到新的窗口L–R更短呢？
L++意味着all++一次，就是又欠了，你刚刚all=0的，现在L++，导致你又欠债了。
那么R就得++了，只有R++才能保证还债继续玩，回到（1）去操作

（5）当R=N时，整个窗口再也没法扩出去了，这时候就终止，你再也找不到更短的了。

看下面的例子：s=cccabab，t=abaccb
all=6，一共欠6个字符，需要s中滑动窗口L–R来还债
当每次R++时，map[c]–,但是保证map[c]>=0，all才能–，代表这是一次有还债；当map[c]<0时，all不能–，因为c还太多了
等R滑动到N-1时，all此时为0，说明L–R刚刚好达标，但是它是不是最短的呢？不是
因为map[s[L]]<0（-1就是小于零，刚刚L–R还太多，说明L开头的串虽然达标，但是不是最短子串）
必须让L++，吐出来c

吐出来之后：看下面蓝色笔
L=1，此时map[c]=0，且，all=0，意味着这就是以L=1开头的串，达标且最短的串，更新min=R-L+1=6-1+1=6，这个就是目前最短的

还有没有更短的呢？
人为让L++，all++；L吞一个c，all=1又欠了一个字符，自然回到（1），需要R++了呗

看下图中粉红色的笔
显然R=N，没有再可以扩的了，所以返回min即可；

整个过程走完，我们在干嘛？？
我们的目标就是完成一个宏观调度，
判断每一个i为开头的达标的最短子串长度不断更新min；
如果达标了，但是不是最短的子串长，我们不需要更新；

代码如下：

//原理就是尝试每一个i==0的位置，找一个达标的覆盖子串，但是过长的咱不需要收集，只要那个最短的

    public static int minWindow(String s, String t){
        if (s == "" || t == "") return 0;//长度为0，覆盖了

        char[] str = s.toCharArray();
        char[] ttr = t.toCharArray();
        int N = str.length;
        int M = ttr.length;

        int[] map = new int[256];
        for (int i = 0; i < M; i++) {
            map[ttr[i]]++;//统计t的词频
        }
        int all = M;//欠的总债务就是t字符串长度
        int L = 0;
        int R = 0;//[L,R)表示我们的窗口位置，最开始R==0不算
        int min = Integer.MAX_VALUE;

        while (R != N){
            //先all>0时R++扩，当str扩到头就结束，没必要让L++，因为长度已经不够了
            //有效还债，all--
            map[str[R]]--;//先减，代表0字符算进来了
            if (map[str[R]] >= 0) all--;//有效的
            //一旦all==0,就要考虑L缩，让多的map拿回来--all再次为1统计结果
            if (all == 0){
                while (map[str[L]] < 0) map[str[L++]]++;//让它拿回来，L++，缩，吐出来
                //知道map全是0，这此时已经是最短的情况了
                min = Math.min(min, R - L + 1);//更新长度最小
                
                //然后，人为的让L++，继续缩，让map继续欠债，all欠债1个字符
                //目标就是想探索下一个L开头的串，可不可能更短呢？？？？？
                map[str[L++]]++;
                all++;//一会出去就只能增加R了---考虑以别的位置i开头时的情况
            }

            //当all>0，继续R++
            R++;
        }

        return min == Integer.MAX_VALUE ? 0 : min;//有这样的最小值才行
    }


    public static void test(){
        String s = "ccbba";
        String t = "abc";//显然cbba最短，怎么着也要4个长度
        System.out.println(minWindow(s, t));
    }

    public static void main(String[] args) {
        test();
    }

总结

提示：重要经验：

1）本题要跳出dp的思想，用欠账策略解决问题
2）哈希表可以用数组表示的，尤其是涉及到字符时，完全可以在ASCII码范围内的数组表示
3）窗口经常配合欠账策略解决词频统计问题。