30. Substring with Concatenation of All Words Leetcode 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).

Solution:

HashMap and "Window"

We use a hashmap to store the counts of all words in Ｌ．　If we use the example given in the question then the hashmap would look like this, foo:1 and bar: 1. 

Then we iterative check the substring with length of word's length in L, in this case, it is 3. 

There are three pointers in this iteration I used in my code: i, start, j. We are not check the S character by character, we iterate it word by word. So for the example the outer looper gonna check the i from 0 to 2, so basically it will check bar,foo,the,foo,bar,man;  arf,oot,hef,oob,arm;  rfo,oth,efo,oba,rma these 3 strings word by word and which will cover all possibilities of concatenation. 

Start is the left side of "window",while j is the right side of "window", for first one"bar,foo,the,foo,bar,man" first word(start-j) is in the hashmap, so we decrease the count of the word, and move the right side window 3(length of a single word) more index. "Window" now is "bar, foo" and the length is the total length of the words, so we found one solution, we can then move the left side of the window the start pointer to right 3 more index and increase the count for corresponding word in the hashmap. Then we can find the next one. 

If during the iteration of window, any word that occur more than once(count=0 when we find the word in the hashmap) we move the left side of the window untill we find the last occurrence of this word and of couse during this process, we need to update the count of corresponding words.

If during the iteration of window, any word that is not in the dictionary, we can simply put the left side of the window to the right side, because for the same i, the window has to be exclude this unwanted word inside itself. 
Time Compleixty: O(m*n) where m is the length of S, n is the length of L, note: left and right side of the window both will only transverse the whole S once. (because they solely move to one direction)

 public List<Integer> findSubstring(String S, String[] L) {  
     List<Integer> res=new ArrayList<Integer>();  
     if(S==null || S.length()==0 || L==null || L.length==0) return res;  
     int ls=S.length();  
     int num=L.length;  
     int ll=L[0].length();  
     if(ll*num>ls) return res;  
     HashMap<String, Integer> map=new HashMap<String,Integer>();  
     for(int i=0;i<num;i++){  
       if(map.containsKey(L[i])){  
         map.put(L[i],map.get(L[i])+1);  
       }  
       else map.put(L[i],1);  
     }  
     HashMap<String, Integer> newMap=new HashMap<String,Integer>(map);  
     for(int i=0;i+ll*num<=ls && i<ll;i++){  
       newMap=new HashMap<String,Integer>(map);  
       int j=i;  
       int start=i;  
       while(j+ll<=ls && start<=ls-num*ll){  
         String temp=S.substring(j,j+ll);  
         if(newMap.containsKey(temp)){  
           int count=newMap.get(temp);  
           if(count==0){  
             while(start<j && !S.substring(start,start+ll).equals(temp)){  
               newMap.put(S.substring(start,start+ll), newMap.get(S.substring(start,start+ll))+1);  
               start+=ll;  
             }  
             start+=ll;  
           }  
           else newMap.put(temp,newMap.get(temp)-1);  
         }  
         else {  
           start=j+ll;  
           newMap=new HashMap<String,Integer>(map);    
         }  
         j=j+ll;  
         if(j-start==num*ll) {  
           res.add(start);  
           if(start+ll<=ls) newMap.put(S.substring(start,start+ll), newMap.get(S.substring(start,start+ll))+1);  
           start+=ll;  
         }  
       }  
     }  
     return res;  
   }