1
class Solution {
2
  // O(sLen + queries.length) time, O(sLen) space
3
  public int[] platesBetweenCandles(String s, int[][] queries) {
4
    int sLen = s.length();
5
    // cumulative number of plates from the left
6
    int[] numberOfPlates = new int[sLen + 1];
7
    for (int i = 0; i < sLen; i++) {
8
      numberOfPlates[i + 1] = numberOfPlates[i] + (s.charAt(i) == '*' ? 1 : 0);
9
    }
10
    // closest candle to the left
11
    int[] candleToTheLeft = new int[sLen];
12
    int cand = -1;
13
    for (int i = 0; i < sLen; i++) {
14
      if (s.charAt(i) == '|') {
15
        cand = i;
16
      }
17
      candleToTheLeft[i] = cand;
18
    }
19
    // closest candle to the right
20
    int[] candleToTheRight = new int[sLen];
21
    cand = -1;
22
    for (int i = sLen - 1; i >= 0; i--) {
23
      if (s.charAt(i) == '|') {
24
        cand = i;
25
      }
26
      candleToTheRight[i] = cand;
27
    }
28
    // for each query - count the number of plates between closest candles
29
    int[] res = new int[queries.length];
30
    for (int i = 0; i < queries.length; i++) {
31
      int left = candleToTheRight[queries[i][0]];
32
      int right = candleToTheLeft[queries[i][1]];
33
      if (left == -1 || right == -1 || left >= right) {
34
        res[i] = 0;
35
      } else {
36
        res[i] = numberOfPlates[right + 1] - numberOfPlates[left];
37
      }
38
    }
39
    return res;
40
  }
41
}