15.7 Substring with Concatenation of All Words

Link: https://oj.leetcode.com/problems/substring-with-concatenation-of-all-words/

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

My thought: Since all the words in L have the same length, I can go through S by the chunk of size in L words. e.g. If words in L has length = 3, we can look at S[0...2], S[3..5], to see if they are contained in L. 

I coded following the approach in . However, I could not code when should we stop searching in S and record the index. 

Approach I: Brute-force

Time: O(m-n)*n) //what is m, what is n???

http://rleetcode.blogspot.com/2014/01/substring-with-concatenation-of-all.html

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(S == null || L == null || S.length() == 0 || L.length == 0){
            return result;
        }
        int wordLen = L[0].length();
        int totalLen = wordLen * L.length; //totalLen of concatenated words in L
        if(S.length() < totalLen) return result;
        HashMap<String, Integer> needToFind = new HashMap<String, Integer>();
        for(String s : L){
            if(needToFind.containsKey(s)){
                needToFind.put(s, needToFind.get(s)+1);
            }
            else{
                needToFind.put(s, 1);
            }
        }
       
        for(int i = 0; i <= S.length()-totalLen; i++){
           if(isValid(needToFind, S, i, wordLen, totalLen)){
               result.add(i);
           }
        }
        return result;
    }
    
    public boolean isValid(HashMap<String, Integer> needToFind, String S, int i, int wordLen, int totalLen){
        HashMap<String, Integer> tmp = new HashMap<String, Integer>(needToFind);
        int start = i;
        int end = i + wordLen;
        while(end - i <= totalLen){
            String sub = S.substring(start, end);
            if(tmp.containsKey(sub)){
                if(tmp.get(sub) == 0){//this word in sub is redundant:"foofoo"
                    return false;
                }
                tmp.put(sub, tmp.get(sub)-1);
                start = end;
                end = start + wordLen;
            }
            else{
                return false;
            }
        }
        return true;
    }
}

Approach II:

http://blog.csdn.net/linhuanmars/article/details/20342851

Assume S.length() = n，L[0].length = l, L.length = m:

Time = O(2*n/l*l)=O(n), Space = O(m*l)

Note: 

• for(int i = 0; i < wordLen; i++) means that we only need to look at the first 0...wordLen-1 chars as start position, since all words after that will be checked. e.g. if S = barfoothefoobarman, L = ["foo", "bar"]. Then we only need to chech "bar, foo, the, ...", or "arf, oot, hef, ..." or "rfo, oth, efo, ...". 
• When the current freq of words in S's substring is larger than that in L

 else{
                        while(curMap.get(sub) > needToFind.get(sub)){
                            String temp = S.substring(left, left + wordLen);
                            curMap.put(temp, curMap.get(temp)-1);
                            left += wordLen;
                        }
                    }

we move the left index forward for one word's length. 

Q: What if S = "foobarbar", L = ["foo", "bar", "foo"]? 

A: In this situation, once we found out that freq(bar) = 2, we move left index from "f" to point to the first "b", since there is no way that "foobarbar" is correct, and it requires that there is no intervening chars.  

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(S == null || L == null || S.length() == 0 || L.length == 0){
            return result;
        }
        int wordLen = L[0].length();
        HashMap<String, Integer> needToFind = new HashMap<String, Integer>();
        for(String s : L){
            if(needToFind.containsKey(s)){
                needToFind.put(s, needToFind.get(s)+1);
            }
            else{
                needToFind.put(s, 1);
            }
        }
       
        for(int i = 0; i <wordLen; i++){
            HashMap<String, Integer> curMap = new HashMap<String, Integer>();
            int count = 0;
            int left = i;
            for(int j = i; j <= S.length() - wordLen; j += wordLen){
                String sub = S.substring(j, j+wordLen);
                if(needToFind.containsKey(sub)){
                    if(!curMap.containsKey(sub)){
                        curMap.put(sub, 1);
                    }
                    else{
                        curMap.put(sub, curMap.get(sub)+1);
                    }
                    if(curMap.get(sub) <= needToFind.get(sub)){
                        count ++;
                    }
                    else{
                        while(curMap.get(sub) > needToFind.get(sub)){
                            String temp = S.substring(left, left + wordLen);
                            curMap.put(temp, curMap.get(temp)-1);
                            left += wordLen;
                        }
                    }
                    if(count == L.length){//found all words in L
                        result.add(left);
                        String temp = S.substring(left, left + wordLen);
                        curMap.put(temp, curMap.get(temp)-1);
                        count --;
                        left+= wordLen;
                    }
                }
                else{//word sub is not in L
                    curMap.clear();
                    count = 0;
                    left = j + wordLen;
                }
            }
         
        }
        return result;
    }
}