1
class Solution {
2
  public List<Integer> findSubstring(String s, String[] words) {
3

4
    HashMap<String, Integer> input = new HashMap<>();
5
    int ID = 1;
6
    HashMap<Integer, Integer> count = new HashMap<>();
7
    for (String word : words) {
8
      if (!input.containsKey(word)) input.put(word, ID++);
9
      int id = input.get(word);
10
      count.put(id, count.getOrDefault(id, 0) + 1);
11
    }
12
    int len = s.length();
13
    int wordLen = words[0].length();
14
    int numWords = words.length;
15
    int windowLen = wordLen * numWords;
16
    int lastIndex = s.length() - windowLen;
17

18
    int curWordId[] = new int[len];
19
    String cur = " " + s.substring(0, wordLen - 1);
20

21
    // Change to int array
22
    for (int i = 0; i < (len - wordLen + 1); i++) {
23
      cur = cur.substring(1, cur.length()) + s.charAt(i + wordLen - 1);
24
      if (input.containsKey(cur)) {
25
        curWordId[i] = input.get(cur);
26
      } else {
27
        curWordId[i] = -1;
28
      }
29
    }
30
    List<Integer> res = new ArrayList<>();
31

32
    // compare using int make it faster 30 times in each comparison
33
    for (int i = 0; i <= lastIndex; i++) {
34

35
      HashMap<Integer, Integer> winMap = new HashMap<>();
36
      for (int j = 0; j < windowLen && curWordId[i] != -1; j += wordLen) {
37

38
        int candidate = curWordId[j + i];
39

40
        if (!count.containsKey(candidate)) break;
41
        else {
42
          winMap.put(candidate, winMap.getOrDefault(candidate, 0) + 1);
43
        }
44
        if (winMap.get(candidate) > count.get(candidate)) break;
45

46
        if (j == (windowLen - wordLen) && winMap.size() == count.size()) {
47
          res.add(i);
48
        }
49
      }
50
    }
51

52
    return res;
53
  }
54
}