1
class Solution {
2
  public int[] movesToStamp(String stamp, String target) {
3

4
    /*
5
     * Intitution:
6
     * Instead of creating target string from intial state,
7
     * create the intial state from the target string.
8
     * - take a window of stamp length
9
     * - reverse that window to the intail state
10
     *  current state -> abcdefgh, window = def,
11
     *  next state    -> abc???gh
12
     *
13
     */
14

15
    int sLen = stamp.length();
16
    int tLen = target.length();
17

18
    // it save the index of reversed charcacter
19
    Queue<Integer> reversedCharIndices = new LinkedList();
20

21
    // it mark Character of target, as reversed
22
    boolean[] isReversedCharOfThisIndex = new boolean[tLen];
23

24
    Stack<Integer> stack = new Stack();
25

26
    List<Window> widowList = new ArrayList();
27

28
    for (int windowStartIndex = 0; windowStartIndex <= tLen - sLen; windowStartIndex++) {
29

30
      Set<Integer> matched = new HashSet();
31
      Set<Integer> notMatched = new HashSet();
32

33
      for (int j = 0; j < sLen; j++) {
34

35
        // char index of current window of the target
36
        int charIndex = windowStartIndex + j;
37

38
        if (stamp.charAt(j) == target.charAt(charIndex)) {
39
          matched.add(charIndex);
40
        } else {
41
          notMatched.add(charIndex);
42
        }
43
      }
44

45
      // add the window
46
      widowList.add(new Window(matched, notMatched));
47

48
      // when all char of current window is matched with
49
      if (notMatched.isEmpty()) {
50
        stack.push(windowStartIndex);
51

52
        for (int index : matched) {
53
          if (!isReversedCharOfThisIndex[index]) {
54

55
            // add in queue, so that we can process,
56
            // another window which is affected by its character get reversed
57
            reversedCharIndices.add(index);
58

59
            // mark it reversed
60
            isReversedCharOfThisIndex[index] = true;
61
          }
62
        }
63
      }
64
    }
65

66
    // get all char index, one by once
67
    // see the impact of reverse char of this index, in ano
68
    while (!reversedCharIndices.isEmpty()) {
69
      int reversedCharIndex = reversedCharIndices.remove();
70

71
      int start = Math.max(0, reversedCharIndex - sLen + 1);
72
      int end = Math.min(reversedCharIndex, tLen - sLen);
73

74
      for (int windowIndex = start; windowIndex <= end; windowIndex++) {
75

76
        if (widowList.get(windowIndex).notMatched.contains(reversedCharIndex)) {
77

78
          // as this char is reversed in another window
79
          // remove this char index from current window,
80
          widowList.get(windowIndex).notMatched.remove(reversedCharIndex);
81

82
          if (widowList.get(windowIndex).notMatched.isEmpty()) {
83

84
            // as all of charcater reversed of current window
85
            // now add current window index
86
            stack.push(windowIndex);
87

88
            for (int index : widowList.get(windowIndex).matched) {
89

90
              if (!isReversedCharOfThisIndex[index]) {
91

92
                // add in queue, so that we can process,
93
                // another window which is affected by its character get reversed
94
                reversedCharIndices.add(index);
95

96
                // mark it reversed
97
                isReversedCharOfThisIndex[index] = true;
98
              }
99
            }
100
          }
101
        }
102
      }
103
    }
104

105
    for (boolean reversed : isReversedCharOfThisIndex) {
106
      if (!reversed) {
107
        return new int[0];
108
      }
109
    }
110

111
    int i = 0;
112
    int[] result = new int[stack.size()];
113
    while (!stack.empty()) {
114
      result[i++] = stack.pop();
115
    }
116

117
    return result;
118
  }
119
}
120

121
class Window {
122
  Set<Integer> matched;
123
  Set<Integer> notMatched;
124

125
  public Window(Set<Integer> matched, Set<Integer> notMatched) {
126
    this.matched = matched;
127
    this.notMatched = notMatched;
128
  }
129
}