There is a long table with a line of plates and candles arranged on top of it. You are given a 0-indexed string s consisting of characters '*' and '|' only, where a '*' represents a plate and a '|' represents a candle.

You are also given a 0-indexed 2D integer array queries where queries[i] = [lefti, righti] denotes the substring s[lefti...righti] (inclusive). For each query, you need to find the number of plates between candles that are in the substring. A plate is considered between candles if there is at least one candle to its left and at least one candle to its right in the substring.


	For example, s = "||**||**|*", and a query [3, 8] denotes the substring "*||**|". The number of plates between candles in this substring is 2, as each of the two plates has at least one candle in the substring to its left and right.


Return an integer array answer where answer[i] is the answer to the ith query.

&nbsp;
Example 1:

Input: s = "**|**|***|", queries = [[2,5],[5,9]]
Output: [2,3]
Explanation:
- queries[0] has two plates between candles.
- queries[1] has three plates between candles.


Example 2:

Input: s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
Output: [9,0,0,0,0]
Explanation:
- queries[0] has nine plates between candles.
- The other queries have zero plates between candles.


&nbsp;
Constraints:


	3 &lt;= s.length &lt;= 105
	s consists of '*' and '|' characters.
	1 &lt;= queries.length &lt;= 105
	queries[i].length == 2
	0 &lt;= lefti &lt;= righti &lt; s.length


class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        psum, next, prev = [0] * (len(s) + 1), [inf] * (len(s) + 1), [0] * (len(s) + 1)
        res = []
        for i, ch in enumerate(s):
            psum[i + 1] = psum[i] + (ch == '|')
            prev[i + 1] = i if ch == '|' else prev[i]
        for i, ch in reversed(list(enumerate(s))):
            next[i] = i if ch == '|' else next[i + 1]
        for q in queries:
            l, r = next[q[0]], prev[q[1] + 1]
            res.append(r - l - (psum[r] - psum[l]) if l < r else 0)
        return res
class Solution {
    // O(sLen + queries.length) time, O(sLen) space
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int sLen = s.length();
        // cumulative number of plates from the left
        int[] numberOfPlates = new int[sLen+1];
        for (int i=0; i<sLen; i++) {
            numberOfPlates[i+1] = numberOfPlates[i] + (s.charAt(i) == '*' ? 1 : 0);
        }
        // closest candle to the left
        int[] candleToTheLeft = new int[sLen];
        int cand = -1;
        for (int i=0; i<sLen; i++) {
            if (s.charAt(i) == '|') {
                cand = i;
            }
            candleToTheLeft[i] = cand;
        }
        // closest candle to the right
        int[] candleToTheRight = new int[sLen];
        cand = -1;
        for (int i=sLen-1; i>=0; i--) {
            if (s.charAt(i) == '|') {
                cand = i;
            }
            candleToTheRight[i] = cand;
        }
        // for each query - count the number of plates between closest candles
        int[] res = new int[queries.length];
        for (int i=0; i<queries.length; i++) {
            int left = candleToTheRight[queries[i][0]];
            int right = candleToTheLeft[queries[i][1]];
            if (left == -1 || right == -1 || left >= right) {
                res[i] = 0;
            } else {
                res[i] = numberOfPlates[right+1] - numberOfPlates[left];
            }
        }
        return res;
    }
}
class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        vector<int> candlesIndex;
        
        for(int i=0;i<s.length();i++){
            if(s[i] == '|')
                candlesIndex.push_back(i);
        }
        
        vector<int> ans;
        for(auto q : queries){
            int firstCandleIndex = lower_bound(candlesIndex.begin() , candlesIndex.end() , q[0]) - candlesIndex.begin();
            int lastCandleIndex = upper_bound(candlesIndex.begin() , candlesIndex.end() , q[1]) - candlesIndex.begin() - 1;
            
            if(lastCandleIndex <= firstCandleIndex){
                ans.push_back(0);
                continue;
            }
                
            
            int tempAns = candlesIndex[lastCandleIndex] - candlesIndex[firstCandleIndex] - (lastCandleIndex - firstCandleIndex);
            
            ans.push_back(tempAns);
        }
        return ans;
    }
};
// time O(N + M) Space O(N) N = s.length M = query.length
var platesBetweenCandles = function(s, queries) {
    let platPreFixSum = [...Array(s.length + 1)];
    let leftViewCandle = [...Array(s.length + 1)];
    let rightViewCandle = [...Array(s.length + 1)];

    platPreFixSum[0] = 0;
    leftViewCandle[0] = -1;
    rightViewCandle[s.length] = -1;

    for(let i = 1; i <= s.length; i++){
        platPreFixSum[i] = s[i-1] == '*' ? platPreFixSum[i - 1] + 1 : platPreFixSum[i - 1];
        leftViewCandle[i] = s[i - 1] == '|' ? i - 1 : leftViewCandle[i - 1];
        rightViewCandle[s.length - i] = s[s.length - i] == '|' ? s.length - i : rightViewCandle[s.length - i + 1];
    }

    let result = [];

    queries.forEach(([left, right]) => {
        if(rightViewCandle[left] >= 0 && leftViewCandle[right + 1] >= 0 &&
           rightViewCandle[left] < leftViewCandle[right + 1]) {
            result.push(platPreFixSum[leftViewCandle[right + 1]] - platPreFixSum[rightViewCandle[left]]);
        } else {
            result.push(0);
        }
    });

    return result;

};
Plates Between Candles