Substring with Concatenation of All Words

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

Algorithm:
It needs 2 mappers
1: look up string in L
2: keep track of the count of string in L that has been seen because string in L can be duplicate.

In general, traverse through the whoel S from beginng to end, and seach substring from L.
*/

import java.util.*;
class FindSubstring {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Integer> ret = new ArrayList<Integer>();

        int sLen = S.length();
        int lLen = L.length;
        if( L.length == 0 ) return ret;
        int llen = L[0].length();
        int totalLen = lLen * llen;

        if(totalLen > sLen) return ret;

        // create a map for L
        HashMap<String, Integer> mapL = new HashMap<String, Integer>();
        for(int i = 0; i < L.length; i++) {
            if(mapL.containsKey(L[i])) {
                mapL.put(L[i], mapL.get(L[i])+1);
            } else {
                mapL.put(L[i], 1);
            }
        }

        // Loop through S to find the match on L
        for(int i = 0; i <= S.length() - llen; i++) {
            // another map for checking how many have been seen from L
            HashMap<String, Integer> seen = new HashMap<String, Integer>();
            String first = S.substring(i, i+llen);
            if(mapL.containsKey(first)) {
                int j = 1;
                seen.put(first, 1);
                for(; j < L.length; j++) {
                    int base = i+j*llen;
                    if(base+llen > S.length()) break;
                    String substr = S.substring(base, base+llen);

                    if(!mapL.containsKey(substr)) break;

                    // increase the count for string in L that has been seen
                    if(seen.containsKey(substr)) {
                        seen.put(substr, seen.get(substr)+1);
                    } else {
                        seen.put(substr, 1);
                    }

                    if(mapL.get(substr) < seen.get(substr)) break;
                }
                if(j == L.length) ret.add(i);
            }
        }

        return ret;
    }
    public static void main(String[] args) {
        // Start typing your code here...
        System.out.println("Hello world!");
        FindSubstring sol = new FindSubstring();
        String[] L = {"a","b","a"};
        System.out.println(sol.findSubstring("abababab", L)); // 0 2 4
    }
}