0030.串联所有单词的子串

https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

方法一：滑动窗口

设字符串 s 长度为 n，数组 words 长度为 m，数组中每个单词长度为 w，则时间复杂度 $O(w \times n)$，空间复杂度 $O(m \times w)$。

func findSubstring(s string, words []string) []int {
	ans, exist, n, m, w := []int{}, map[string]int{}, len(s), len(words), len(words[0])
	for _, w := range words {
		exist[w]++
	}
	for i := 0; i < w; i++ {
		help := map[string]int{}
		for j, k := i, i+w-1; k < n; k += w {
			sub := s[k-w+1 : k+1]
			help[sub]++
			if k-j+1 < m*w {
				continue
			}
			cnt := 0
			for key := range exist {
				if exist[key] == help[key] {
					cnt++
				}
			}
			if cnt == len(exist) {
				ans = append(ans, j)
			}
			help[s[j:j+w]]--
			j += w
		}
	}
	return ans
}

func findSubstring(s string, words []string) []int {
	ans, exists, n, m, w := []int{}, map[string]int{}, len(s), len(words), len(words[0])
	for _, b := range words {
		exists[b]++
	}
	for i := 0; i < w; i++ {
		cnt, help := 0, map[string]int{}
		for l, r := i, i+w-1; r < n; r += w {
			pre, post := s[l:l+w], s[r-w+1:r+1]
			help[post]++
			if exists[post] >= help[post] {
				cnt++
			}
			if r-l+1 < m*w {
				continue
			}
			if cnt == m {
				ans = append(ans, l)
			}
			help[pre]--
			l += w

			if exists[pre] > help[pre] {
				cnt--
			}
		}
	}
	return ans
}