Plates Between Candles

The most efficient approach involves pre-calculating all the necessary information to answer each query in constant time. We can precompute not only the prefix sums of plates but also the positions of the nearest candles for every index in the string.

• First, perform a full precomputation step in O(N) time:
  1. Create a prefix sum array prefixPlates of size n. prefixPlates[i] stores the count of '*' in s[0...i].
  2. Create an array prevCandle of size n. prevCandle[i] stores the index of the closest candle to the left of or at index i. This is computed in a single pass from left to right.
  3. Create an array nextCandle of size n. nextCandle[i] stores the index of the closest candle to the right of or at index i. This is computed in a single pass from right to left.
• Initialize an answer array.
• For each query [left, right]:
  • Find the effective left boundary candle index: startCandle = nextCandle[left].
  • Find the effective right boundary candle index: endCandle = prevCandle[right].
  • Check if these boundaries are valid and if startCandle < endCandle.
  • If they are, the number of plates is prefixPlates[endCandle] - prefixPlates[startCandle]. This is an O(1) operation.
  • If the boundaries are not valid, the answer is 0.
• Return the answer array.

This approach achieves the optimal time complexity by performing a thorough precomputation. The key idea is to answer every query in constant time by having all the required information readily available in lookup tables (arrays).

We create three auxiliary arrays:

1. prefixPlates: As in the previous approach, prefixPlates[i] stores the cumulative number of plates up to index i.
2. nextCandle: For each index i, nextCandle[i] stores the index of the first candle encountered when moving from i to the right. This can be computed with a single pass from right to left.
3. prevCandle: For each index i, prevCandle[i] stores the index of the first candle encountered when moving from i to the left. This is computed with a pass from left to right.

After this O(N) precomputation, each query [left, right] can be resolved instantly. The true left boundary is nextCandle[left], and the true right boundary is prevCandle[right]. If these boundaries are valid, the plate count is a simple lookup and subtraction using the prefixPlates array.

class Solution {
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int n = s.length();
        
        int[] prefixPlates = new int[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '*') {
                count++;
            }
            prefixPlates[i] = count;
        }
        
        int[] prevCandle = new int[n];
        int lastCandle = -1;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '|') {
                lastCandle = i;
            }
            prevCandle[i] = lastCandle;
        }
        
        int[] nextCandle = new int[n];
        int firstCandle = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '|') {
                firstCandle = i;
            }
            nextCandle[i] = firstCandle;
        }
        
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int left = queries[i][0];
            int right = queries[i][1];
            
            int startCandle = nextCandle[left];
            int endCandle = prevCandle[right];
            
            if (startCandle != -1 && endCandle != -1 && startCandle < endCandle) {
                ans[i] = prefixPlates[endCandle] - prefixPlates[startCandle];
            } else {
                ans[i] = 0;
            }
        }
        
        return ans;
    }
}