Substring with Concatenation of All Words

SubstringwithConcatenationofAllWords.java

/**
 * You are given a string, S, and a list of words, L, that are all of the same length. 
 * Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
 * For example, given:
 * S: "barfoothefoobarman"
 * L: ["foo", "bar"]
 * You should return the indices: [0,9].
 * (order does not matter).
 */
public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> indices = new ArrayList<Integer>();
        if (L.length == 0) 
            return indices;
        // notice: all the same length
        int total = L.length, wordLen = L[0].length();
        // Store the words and frequences in a hash table for L array
        HashMap<String, Integer> words = new HashMap<String, Integer>();
        for (String s : L) {
            if(words.containsKey(s)) 
                words.put(s, words.get(s) + 1);
            else 
                words.put(s, 1);
        }
        // find the concatenations
        for (int i = 0; i <= S.length() - total * wordLen; i++) {
            // check if it is a concatenation
            HashMap<String, Integer> target = new HashMap<String, Integer>(words);
            for (int j = i; j <= S.length() - wordLen && !target.isEmpty(); j += wordLen) {
                String sub = S.substring(j, j + wordLen);
                if(!target.containsKey(sub))
                    break;
                else if (target.get(sub) > 1) {
                    // reduce the frequency
                    target.put(sub, target.get(sub) - 1);
                } else {
                    // remove the word if only one left
                    target.remove(sub);
                }
            }
            if (target.isEmpty()) {
                indices.add(i);
            }
        }
        return indices;
    }
    
    
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
        if(words.length == 0) return res;
        int count = words.length, wordLen = words[0].length();
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for(String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        HashMap<String, Integer> found = new HashMap<String, Integer>();
        for(int i = 0; i <= s.length() - count * wordLen; i++) {
            found.clear();
            for(int j = 0; j < count; j++) {
                int k = i + j * wordLen;
                String str = s.substring(k, k + wordLen);
                if(!map.containsKey(str))  break;
                found.put(str, found.getOrDefault(str, 0) + 1);
                if(found.get(str) > map.get(str)) break;
                if(j == count - 1) res.add(i);
            }
        }
         return res;
    }
}