2055. Plates Between Candles

class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        int n = s.size();
        vector<int> previousCandle(n, -1);      // Closest candle to the left
        vector<int> nextCandle(n, -1);          // Closest candle to the right
        vector<int> platePrefixSum(n + 1, 0);
        
        // Build previousCandle array (scan left to right)
        int lastCandle = -1;
        for(int i = 0; i < n; i++){
            if(s[i] == '|') lastCandle = i;
            previousCandle[i] = lastCandle;
        }
        
        // Build nextCandle array (scan right to left)  
        lastCandle = -1;
        for(int i = n - 1; i >= 0; i--){
            if(s[i] == '|') lastCandle = i;
            nextCandle[i] = lastCandle;
        }
        
        // Build prefix sum array - number of plates from 0 to i-1
        for(int i = 0; i < n; i++){
            platePrefixSum[i + 1] = platePrefixSum[i] + ((s[i] == '*') ? 1 : 0);
        }
        
        vector<int> result;
        for(auto &query: queries){
            int left = query[0], right = query[1];
            int leftCandle = nextCandle[left];        // First candle >= left
            int rightCandle = previousCandle[right];  // Last candle <= right
            
            if(leftCandle != -1 && rightCandle != -1 && leftCandle < rightCandle) {
                // Count plates between the two candles
                int plateCount = platePrefixSum[rightCandle] - platePrefixSum[leftCandle];
                result.push_back(plateCount);
            } else {
                result.push_back(0); 
            }
        }
        return result;
    }
};