Problem Description

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.

Solution

The first subproblem is given a substring, how we can quickly check if it is a concatenated substring? The answer is to count the words in the substring and compare to words. So we can check all substrings.

And next, how we can optimize it? It turns out there are too many repetitions when we are doing checks, then using sliding windows can help with it. Since all words are the same length, we can go forward one word each time, at the same time, taking care of the word to be removed and the word to be added. There are many improvements: for example, whenever we encounter an unmatched word, we could just skip it and restart at the next word; whenever we find a matched word appearing more times, we could just keep moving forward such that the excess words get removed (not implemented in the code below).

Java Code

Checking all possible substrings

class Solution {
    private Map<String, Integer> map = new HashMap<>();
    private int valid_size, len, word_size;
    public List<Integer> findSubstring(String s, String[] words) {
        int s_size = s.length();
        List<Integer> res = new ArrayList<>();
        len = words.length;
        word_size = words[0].length();
        valid_size = len*word_size;
        for(int i=0; i<len; i++){
            map.put( words[i], map.getOrDefault(words[i],0)+1 );
        }
        for(int i=0; i<=s_size-valid_size; i++){
            if( checkValidString(s, i) ) res.add(i);
        }
        return res;
    }

    private boolean checkValidString(String s, int start_ind){
        Map<String, Integer> words_count = new HashMap<>(map);
        for(int i=start_ind; i<start_ind+valid_size; i+=word_size){
            String str = s.substring(i, i+word_size);
            int count = words_count.getOrDefault(str,0);
            if( count > 0 ) words_count.put(str, count-1 );
            else return false;
        }
        return true;
    }
}

Sliding Window

class Solution {
    private Map<String, Integer> map = new HashMap<>();
    private int valid_size, len, word_size, s_size;
    List<Integer> res = new ArrayList<>();
    public List<Integer> findSubstring(String s, String[] words) {
        s_size = s.length();
        len = words.length;
        word_size = words[0].length();
        valid_size = len*word_size;
        if(s_size < valid_size) return res;
        for(int i=0; i<len; i++){
            map.put( words[i], map.getOrDefault(words[i],0)+1 );
        }

        for(int i=0; i<word_size; i++){
            if(i+valid_size <= s_size) checkValidString(s, i);
        }
        return res;
    }

    private void checkValidString(String s, int start_ind){
        Map<String, Integer> words_count = new HashMap<>(map);
        int valid_count = 0, i = start_ind;
        for(;i<=s_size-word_size;i+=word_size){
            if(i-start_ind>=valid_size){
                String str_rmv = s.substring(i-valid_size, i-valid_size+word_size);
                if(map.containsKey(str_rmv)){
                    if( words_count.getOrDefault(str_rmv,0) >= 0 ) valid_count --;
                    words_count.put( str_rmv, words_count.getOrDefault(str_rmv,0)+1 );
                }
            }
            String str_add = s.substring(i, i+word_size);
            int count = words_count.getOrDefault(str_add,0);
            if(map.containsKey(str_add)){
                if( count > 0 ) valid_count ++;
                words_count.put(str_add, count-1 );
            }else{
                // unmatch words, reset, but resetting map is very costly
                //valid_count = 0;
                //for(String k:map.keySet()) words_count.put(k, map.get(k));
                //start_ind = i+word_size;
                //continue;
                ;
            }
            if(valid_count == len) res.add(i-valid_size+word_size);
        }
    }
}