Question

link

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

Stats

Frequency 1
Diffficulty 3
Adjusted Difficulty 4
Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

There are 2 ways to solve this question.

The naive approach takes around 1200ms to pass, and the KPM-like approach takes around half of that time. Both methods are explained well in this blog.

I will cover only the naive approach.

Naive approach

The naive approach uses a HashMap for 2 reasons. Reason 1 is because there can be duplications in L, and reason 2 is the searching is faster. For information on HashMap, refer to [Fundamental] Recap on Java HashMap.

Time complexity of this solution is O((n - k * m) x m), and space is the size of list L, O(m). If m is not very big, the time can be regarded as O(n).

My code

public class Solution {
    public List<Integer> findSubstring(String S, String[] L) {
        List<Integer> ans = new ArrayList<Integer>();
        if (L == null || L.length == 0 || S == null || S.length() == 0) {
            return ans;
        }
        int num = L.length;
        int len = L[0].length();
        if (num * len > S.length()) {
            return ans;
        }
        // build a hashset, for simplifying the hashmap generation later on
        HashMap<String, Integer> set = new HashMap<String, Integer>();
        for (String str: L) {
            if (set.containsKey(str)) {
                set.put(str, set.get(str) + 1);
            } else {
                set.put(str, 1);
            }
        }
        // starting from i, check Concatenation of All Words
        for (int i = 0; i <= S.length() - (num * len); i++) {
            // first build a HashMap from the set that we acquired before
            HashMap<String, Integer> map = new HashMap<String, Integer>(set);
            for (int j = 0; j < num; j++) {
                String str = S.substring(i + j * len, i + (j + 1) * len);
                if (!map.containsKey(str)) {
                    break;
                } else if (map.get(str) > 1) {
                    map.put(str, map.get(str) - 1);
                } else if (map.get(str) == 1) {
                    map.remove(str);
                }
            }
            if (map.isEmpty()) {
                ans.add(i);
            }
        }
        return ans;
    }
}