class Solution {
    // time O(n)
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int[] prefixSum = new int[s.length()];
        int count = 0;
        int[] nearestLeftCandle = new int[s.length()];
        int[] nearestRightCandle = new int[s.length()];
        int lastLeftCandleIndex = -1;
        int lastRightCandleIndex = -1;
        for (int i = 0; i < s.length(); i++) {
            // Count the number of stars so far at each index
            if (s.charAt(i) == '*') {
                count++;
            }
            prefixSum[i] = count;

            // Keep track of indices for the nearest left and right candle
            if (s.charAt(i) == '|') {
                lastLeftCandleIndex = i;
            }
            nearestLeftCandle[i] = lastLeftCandleIndex;

            if (s.charAt(s.length() - i - 1) == '|') {
                lastRightCandleIndex = s.length() - i - 1;
            }
            nearestRightCandle[s.length() - i - 1] = lastRightCandleIndex;
        }

        int[] counts = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int[] query = queries[i];

            int leftCandleIndex = nearestRightCandle[query[0]];
            int rightCandleIndex = nearestLeftCandle[query[1]];

            if (leftCandleIndex == -1 || rightCandleIndex == -1 || leftCandleIndex >= rightCandleIndex) {
                counts[i] = 0;
            }
            else {
                counts[i] = prefixSum[rightCandleIndex] - prefixSum[leftCandleIndex];
            }
        }

        return counts;
    }
}