# Question

Formatted question description: https://leetcode.ca/all/30.html

30. Substring with Concatenation of All Words

You are given a string, s, and a list of words, words, that are all of the same length.

Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once
and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

@tag-string


# Algorithm

It is necessary to frequently judge whether the substring of length len in the s string is a word in words. For quick judgment, you can use HashMap. At the same time, because the words array may have repeated words, you must use HashMap to create all words and their appearance times The mapping between, that is, count the number of times each word appears.

Traverse all the substrings of length nxlen in s. When the length of the remaining substrings is less than nxlen, there is no need to judge. So i starts from 0 and ends at (int)s.size()-nxlen. Note that you must first convert s.size() to an integer before performing the solution. Be sure to form such a habit. Once size() is to be subtracted from a number, first switch to int type, because the return value of size() is unsigned.

Once you subtract a number larger than yourself, an error will occur. For each traversed substring of length nxlen, it is necessary to verify whether it is exactly composed of all words in words. The checking method is to take the substring of length len each time to see if it is a word in words. To facilitate comparison, create another HashMap.

When the extracted word is not in words, break it directly, otherwise, add 1 to its mapping value in the new HashMap, and check if its mapping value exceeds the mapping value in the original HashMap, Also break off, because even if the current word is in words, if it appears more than the number of times in words, it is still unsatisfactory. Outside the for loop, if j is exactly equal to n, it means that the detected n substrings of length len are all words in words, and just form words, then the current position i is added to the result.

Java