Here is a long table with plates and candles lined up on it. Give you a string s with subscript starting from 0 |, which contains only the characters' * 'and' | ', where' * 'represents a plate and' | 'represents a candle.

At the same time, you will be given a two-dimensional integer array {queries with subscript starting from 0}, where {queries[i] = [lefti, righti] represents the substring} s[lefti...righti] (including the characters of the left and right endpoints). For each query, you need to find the number of plates in the substring between two candles. If a plate has at least one candle on the left and right of the substring, the plate is satisfied between the two candles.

For example, s = "* * * *", query [3, 8], which represents the substring "* * *". The number of plates between two candles in the substring is 2, and the two plates on the right in the substring have at least one candle on their left and right.
Please return an integer array ， answer, where ， answer[i] is the answer to the ， I ， th query.

Example 1:

Input: S = "* * * * * * * *", queries = [[2,5], [5,9]]
Output: [2,3]
Explanation:
-There are two plates between the candles.
-There are three plates between the 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] there are nine plates between the candles.
-Another query has no plates between candles.

Topic idea:

Record prefix and, in short, record the total number from the starting point to each position*
Take two more arrays and a right to record the position of | on the left and right
A left records the position of the left | at the right end
The process of recording the position is the process of traversing the string. The coordinates of each | are recorded from the left to the previous | and the same is true for the right
Establish the learning process, print out the values of left and right, and you can see that it is actually very simple

Python code:

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)#Find the length of the string
        #first is used to record prefixes and. In short, it is used to record the total number of prefixes from the starting point to each position*
        first , left , right = [0]*(n+1) , [-1]*n , [-1]*n  #The reason why the initial values of left and right are assigned to 1 is
        #Because it is necessary to judge whether the left and right are greater than 0|
        #Left is used to record the serial number of the nearest | on the left of each position
        #Right is used to record the serial number of the nearest | position on the right of each position
        l , r = -1 , -1
        for i , j in enumerate(s):
            if j == "*":             #first is used to record prefixes and. In short, it is used to record the total number of prefixes from the starting point to each position*
               first[i+1] = first[i] + 1  #If the current position is * then the number of next positions is the current + 1
            else:
               first[i+1] = first[i]   #If not * the number of * corresponding to the next coordinate is equal to this one
               l = i 
            left[i] = l   #  Assign the coordinates of the previous one until you meet the next one
        for i , j in enumerate(s[::-1]):     #Reverse traversal
            if j == "|":          #ditto
               r = n-1-i
            right[n-1-i] = r
            
        return [first[left[r]] - first[right[l]] if left[r]>=0 and right[l]>=0 and left[r]>right[l] else 0 for l , r in queries]
        #Traverse the queries and then judge the situation at each position. If the value on the right side of the left end of the coordinate is less than 0 or the value on the left side of the right end is less than 0, 0 will be output


               

           

C + + Code:

class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        int n = s.length(); //Find the length of the string
        vector<int> prnum(n+1); //prnum is used to record prefixes and. In short, it is used to record the total number of prefixes from the starting point to each position*
        vector<int> left(n);//Create an empty left array
        vector<int> right(n);  //Create an empty right array
        vector<int> ans;//Left is used to record the serial number of the nearest | position on the left of each position #right is used to record the serial number of the nearest | position on the right of each position
        for (int i=0 , l=-1; i<n; i++){
            if (s[i] == '*'){   //first is used to record prefixes and. In short, it is used to record the total number of prefixes from the starting point to each position*
                prnum[i+1] = prnum[i] + 1;  //If * the current position is + 1, then the next number is
            }
            else{
                prnum[i+1] = prnum[i];//If not * the number of * corresponding to the next coordinate is equal to this one
                l = i;
            }
            left[i] = l;   //Assign the coordinates of the previous one until you meet the next one
        }
        for (int i=n-1 , r=-1; i>=0; i--)  {                                                                                                                                      
            if (s[i] == '|'){     //Reverse traversal
                r = i;
            }
            right[i] = r;//ditto
        }
        for (auto& query : queries){
            int x = right[query[0]] , y = left[query[1]];
            ans.push_back(x<0 || y<0 || x>=y ?0:prnum[y] - prnum[x]);
        }
        //#Traverse the queries and then judge the situation at each position. If the value on the right side of the left end of the coordinate is less than 0 or the value on the left side of the right end is less than 0, 0 will be output
        return ans;
    }
};