30. 串联所有单词的子串

思路

参考灵神30 次定长滑动窗口（Python/Java/C++/Go/JS/Rust）

因为题目要求的串联子串长度固定，并且为words中所有字符串以任意顺序连接，我们可以想到使用定长的滑动窗口。

我们可以维护两个哈希表，一个用来表示words里字符串出现的次数，一个用来存储加入到滑动窗口的字符串及次数。

由于words中的字符串长度相同，我们需要做的每次将窗口移动这个距离。

首先，不断将这个长度的子串加入到哈希表中。如果我们加入了不在words里的表，或者加入了这个字符串之后出现的次数大于words里出现的次数，我们将overload的标记加一，表示多了一个不符合的字符串。这样，当overload等于0且滑动窗口左端至少在字符串s中时，我们就得到了一个串联子串。

需要进行的特判是，如果左端index小于0，证明滑动窗口还不完整，这时候我们不判定overload。

然后，如果最左边有字符串，将最左边的子串在哈希表的记录减一，如果是不符合的字符串则overload对应地减少一个。

最后需要注意的是，对于一个起始点i，我们使用步长为l的滑动窗口，只能检查到所有i + k * l的起始点，这样我们可能会漏掉一些起始点。为了解决这个问题，我们做l次滑动窗口，起始点从0一直到l - 1，这样我们就不会漏掉起始点。

总结来说，对于固定滑动窗口的题目，主体的框架就是入滑窗、检查是否符合、出滑窗，其他的小细节就是左端判断以及滑动次数。

代码

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int wordLen = words[0].length(); // 一个单词的长度
        int windowLen = wordLen * words.length; // 所有单词的总长度，即窗口大小

        // 目标：窗口中的单词出现次数必须与 targetCnt 完全一致
        Map<String, Integer> targetCnt = new HashMap<>();
        for (String w : words) {
            targetCnt.merge(w, 1, Integer::sum); // targetCnt[w]++
        }

        List<Integer> ans = new ArrayList<>();
        // 枚举窗口起点，做 wordLen 次滑动窗口
        for (int start = 0; start < wordLen; start++) {
            Map<String, Integer> cnt = new HashMap<>();
            int overload = 0;
            // 枚举窗口最后一个单词的右端点+1
            for (int right = start + wordLen; right <= s.length(); right += wordLen) {
                // 1. inWord 进入窗口
                String inWord = s.substring(right - wordLen, right);
                // 下面 cnt[inWord]++ 后，inWord 的出现次数过多
                if (cnt.getOrDefault(inWord, 0).equals(targetCnt.getOrDefault(inWord, 0))) {
                    overload++;
                }
                cnt.merge(inWord, 1, Integer::sum); // cnt[inWord]++

                int left = right - windowLen; // 窗口第一个单词的左端点
                if (left < 0) { // 窗口大小不足 windowLen
                    continue;
                }

                // 2. 更新答案
                // 如果没有超出 targetCnt 的单词，那么也不会有少于 targetCnt 的单词
                if (overload == 0) {
                    ans.add(left);
                }

                // 3. 窗口最左边的单词 outWord 离开窗口，为下一轮循环做准备
                String outWord = s.substring(left, left + wordLen);
                cnt.merge(outWord, -1, Integer::sum); // cnt[outWord]--
                if (cnt.get(outWord).equals(targetCnt.getOrDefault(outWord, 0))) {
                    overload--;
                }
            }
        }

        return ans;
    }
}