Leetcode 30 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 wordsexactly 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 1: brute-force, which could pass the worst case. Several improvement can not pass as average time complexity is improved but not the worse case.

 public class Solution {  
   public List<Integer> findSubstring(String s, String[] words) {  
     List<Integer> res=new ArrayList<>();  
     int n=s.length();  
     int m=words.length;  
     if (m==0) return res;  
     int k=words[0].length();  
     if (k==0) return res;  
     if (m*k>n) return res;  
     Map<String,Integer> map=new HashMap<>();  
     for (int i=0; i<m; i++) {  
       if (map.containsKey(words[i])) map.put(words[i],map.get(words[i])+1);  
       else map.put(words[i],1);  
     }  
     for (int i=0; i<=n-m*k; i++) {  
       Map<String,Integer> clone=new HashMap<>();  
       clone.putAll(map);  
       int j=0;  
       while (j<m) {  
         String key=s.substring(i+j*k,i+j*k+k);  
         if (clone.containsKey(key) && clone.get(key)>0) {  
           clone.put(key,clone.get(key)-1);  
           j++;  
         }  
         else break;  
       }  
       if (j==m) res.add(i);  
     }  
     return res;  
   }  
 }  

Solution 1: Use slid window (HashMap+count), O(n*k) complexity, reduce run time

 public class Solution {  
   public List<Integer> findSubstring(String s, String[] words) {  
     List<Integer> res=new ArrayList<>();  
     int n=s.length(), len=words.length;  
     if (n==0 || len==0) return res;  
     int step=words[0].length();  
     if (step==0) return res;  
     Map<String,Integer> map=new HashMap<>();  
     int count=0;  
     for (String word: words) {  
       if (map.containsKey(word)) map.put(word,map.get(word)+1);  
       else {  
         map.put(word,1);  
         count++;  
       }  
     }  
     for (int k=0; k<step; k++) {  
       int i=k;  
       if (i+len*step>n) break;  
       Map<String,Integer> localMap=new HashMap<>(map);  
       int localCount=count;  
       for (int j=i; j<=n-step; j+=step) {  
         String word=s.substring(j,j+step);  
         if (localMap.containsKey(word)) {  
           int num=localMap.get(word);  
           if (num==1) localCount--;  
           else if (num==0) localCount++;  
           localMap.put(word,num-1);  
         }  
         else {  
           localMap.put(word,-1);  
           localCount++;  
         }  
         if (j-i>=len*step) {  
           String preWord=s.substring(i,i+step);  
           int num=localMap.get(preWord);  
           if (num==-1) localCount--;  
           else if (num==0) localCount++;  
           localMap.put(preWord,num+1);  
           i+=step;  
         }  
         if (localCount==0) res.add(i);  
       }  
     }  
     return res;  
   }  
 }