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).

Solution:

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        Map<String, Integer> freq = new HashMap<>();
        for(String w : words){
            if(freq.containsKey(w)) freq.put(w, freq.get(w)+1);
            else freq.put(w, 1);
        }
        List<Integer> ans = new ArrayList<>();
        Map<String, Integer> seen = new HashMap<>();
        int count = 0;
        int wordLen = words[0].length();
        for(int i=0; i<wordLen; i++){
            int start = i;
            for(int j=i; j<=s.length()-wordLen; j+=wordLen){
                String word = s.substring(j, j+wordLen);
                if(freq.containsKey(word)){
                    if(seen.containsKey(word)) seen.put(word, seen.get(word)+1);
                    else seen.put(word, 1);
                    count++;
                    while(seen.get(word)>freq.get(word)){
                        String remove = s.substring(start, start+wordLen);
                        start += wordLen;
                        seen.put(remove, seen.get(remove)-1);
                        count--;
                    }
                    if(count==words.length) ans.add(start);
                } else {
                    count = 0;
                    seen.clear();
                    start = j+wordLen;
                }
            }
            seen.clear();
            count = 0;
        }
        return ans;
    }
}