包含子串的个数

public long chooseMessage(String messages, String keys)求messages中包含keys所有字母的子串（不要求顺序）个数，其中两者都是大写字母组成。

例子：
messages = “ABBCDCDAB”，keys = “BAC”，那么所有符合的字符串为
由ABBC开头及后面的字符串共6个
ABBC
ABBCD
ABBCDC
ABBCDCD
ABBCDCDA
ABBCDCDAB

BBCDCDA：2
BCDCDA：2
CDCDAB：1
DCDAB：1
CDAB：1

思路：
我们只需要找到符合条件的最短字符串即可ABBC、BBCDCDA、BCDCDA、BCDCDA、CDCDAB、DCDAB、CDAB，然后加上自身及后面有的字符串个数（具体实现见下面的count += messages.length() - end + 1;），这种解法类似于连续子区间和

    public long chooseMessage(String messages, String keys) {
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < keys.length(); i++) {
            set.add(keys.charAt(i));
        }

        int numOfDigitsMatched = 0;
        HashMap<Character, Integer> tempMap = new HashMap<>();
        int start = 0;
        int end = 0;
        int count = 0;
        while (end < messages.length()) {
            end += 1;
            char lastChar = messages.charAt(end - 1);

            if (set.contains(lastChar)) {
                tempMap.put(lastChar, tempMap.getOrDefault(lastChar, 0) + 1);

                if (tempMap.get(lastChar) == 1) {
                    numOfDigitsMatched += 1;
                }
                while (numOfDigitsMatched == set.size()) {
                    count += messages.length() - end + 1;

                    char firstChar = messages.charAt(start);
                    if (set.contains(firstChar)) {
                        tempMap.put(firstChar, tempMap.get(firstChar) - 1);
                        if (tempMap.get(firstChar) == 0) {
                            tempMap.remove(firstChar);
                            numOfDigitsMatched -= 1;
                        }
                    }
                    start += 1;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(new ChooseMessage().chooseMessage("ABBCDCDAB", "BAC") == 13);
        System.out.println(new ChooseMessage().chooseMessage("ZZ", "Z") == 3);
        System.out.println(new ChooseMessage().chooseMessage("DFWAW", "GF") == 0);
        System.out.println(new ChooseMessage().chooseMessage("", "A") == 0);
        System.out.println(new ChooseMessage().chooseMessage("A", "A") == 1);
    }