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.
Example :
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9]. (order does not matter).
Solution:
Time: O(S) * O(L) Space: O(L)
public class Solution { // DO NOT MODIFY THE LIST. IT IS READ ONLY public ArrayList<Integer> findSubstring(String A, final List<String> B) { ArrayList<Integer> result = new ArrayList<>(); if (B.size() == 0) return result; int wordSize = B.get(0).length(); Map<String, Integer> map = new HashMap<>(); for (String s : B) { if (map.containsKey(s)) { map.put(s, map.get(s) + 1); } else { map.put(s, 1); } } for (int i = 0; i <= A.length() - B.size() * wordSize; i ++) { Map<String, Integer> m = new HashMap<>(map); int start = i; int end = start + wordSize; while (end - i <= B.size() * wordSize) { String s = A.substring(start, end); if (m.containsKey(s) && m.get(s) > 0) { if (end - i == B.size() * wordSize) { result.add(i); } m.put(s, m.get(s) - 1); start = end; end = start + wordSize; } else { break; } } } return result; } }