You are given a string s and an array of strings words. All the strings of words are of the same length.

 QUESTION:

You are given a string s and an array of strings words. All the strings of words are of the same length. A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated. For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated substring because it is not the concatenation of any permutation of words. Return the starting indices of all the concatenated substrings in s. You can return the answer in any order. Example 1: Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6. The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words. The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words. The output order does not matter. Returning [9,0] is fine too. Example 2: Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] Output: [] Explanation: Since words.length == 4 and words[i].length == 4, the concatenated substring has to be of length 16. There is no substring of length 16 is s that is equal to the concatenation of any permutation of words. We return an empty array. Example 3: Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] Output: [6,9,12] Explanation: Since words.length == 3 and words[i].length == 3, the concatenated substring has to be of length 9. The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"] which is a permutation of words. The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"] which is a permutation of words. The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"] which is a permutation of words. Constraints: 1 <= s.length <= 104 1 <= words.length <= 5000 1 <= words[i].length <= 30 s and words[i] consist of lowercase English letters. Implement with java code. Insert comments

ANSWER:

Here's the Java code with comments to solve the given problem using a sliding window approach:

arduino
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return result; // if s or words is empty or null, return an empty result
        }
        
        Map<String, Integer> freqMap = new HashMap<>(); // map to store the frequency of each word in words
        for (String word : words) {
            freqMap.put(word, freqMap.getOrDefault(word, 0) + 1);
        }
        
        int wordLen = words[0].length(); // length of each word
        int windowSize = wordLen * words.length; // total length of concatenated substring
        
        for (int i = 0; i <= s.length() - windowSize; i++) { // iterate through all possible starting indices of the substring
            Map<String, Integer> seenMap = new HashMap<>(); // map to keep track of the frequency of each word seen so far in the current substring
            
            int j = 0;
            while (j < windowSize) { // slide the window over the current substring
                String word = s.substring(i + j, i + j + wordLen); // get the current word
                if (!freqMap.containsKey(word)) { // if the word is not in words, move to the next starting index
                    break;
                }
                
                seenMap.put(word, seenMap.getOrDefault(word, 0) + 1); // update the frequency of the current word in seenMap
                if (seenMap.get(word) > freqMap.getOrDefault(word, 0)) { // if the current word appears more times than it appears in words, move to the next starting index
                    break;
                }
                
                j += wordLen; // move to the next word in the substring
            }
            
            if (j == windowSize) { // if all words in words are present in the current substring, add the starting index to the result
                result.add(i);
            }
        }
        
        return result;
    }
}