Description

Submission

class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        int n = s.length();
        vector<int> presum(n); // number of plates <= current index
        vector<int> prev(n);   // the previous candle index
        vector<int> next(n);   // the next candle index

        presum[0] = (s[0] == '*');
        for(int i = 1; i < n; ++i) {
            presum[i] = presum[i-1] + (s[i] == '*');
        }

        int curPrev = -1;
        for(int i = 0; i < n; ++i) {
            if(s[i] == '|') curPrev = i;
            prev[i] = curPrev;
        }

        int curNext = n;
        for(int i = n - 1; i >= 0; --i) {
            if(s[i] == '|') curNext = i;
            next[i] = curNext;
        }

        vector<int> rets;
        for(auto& q: queries) {
            int x = q[0], y = q[1];
            int a = next[x], b = prev[y];

            if(a >= x && b <= y && a <= b) {
                rets.push_back(presum[b] - presum[a]);
            } else {
                rets.push_back(0);
            }
        }

        return rets;
    }
};