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 words exactly 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

import java.util.*;

/**
 * Created by ligong on 15/12/2014.
 */
public class Solution {

 public List<Integer> findSubstring(String S, String[] L) {
    List<Integer> result = new ArrayList<Integer>();
        if (S == null || L.length == 0)
            return result;

        if (S.length() < L[0].length() * L.length)
            return result;

        Map<String, Integer> wordLabel = new HashMap<String, Integer>();
        for (int i = 0; i < L.length; i++) {
            if (!wordLabel.containsKey(L[i])) {
                wordLabel.put(L[i], 0);
            }

            wordLabel.put(L[i], wordLabel.get(L[i]) + 1);
        }

        int m = L.length;
        int n = L[0].length();

        int runner = 0;
        while (runner <= S.length() - m * n) {
            int tempResult = check(S, runner, m, n, wordLabel);
            if (tempResult >= 0) {
                result.add(tempResult);
            }

            runner += 1;
        }

        return result;

    }


    public static int check(String target, int start, int m, int n, Map<String, Integer> wordLabels) {

        Map<String, Integer> checkMap = new HashMap<String, Integer>();
        int end = start + (m-1) * n;

        int runner = start;

        while (runner <= end) {
            String current = target.substring(runner, runner + n);
            if (wordLabels.containsKey(current)) {
                if (!checkMap.containsKey(current)) {
                    checkMap.put(current, 1);
                } else {
                    checkMap.put(current, checkMap.get(current) + 1);
                }

                if (wordLabels.get(current) < checkMap.get(current)) {
                    return -1;
                }

            } else {
                return -1;
            }

            runner += n;
        }

        return start;
    }


}