LeetCode 2055. Plates Between Candles

原题链接在这里：https://leetcode.com/problems/plates-between-candles/description/

题目：

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.

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.

Constraints:

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

题解：

The request is give a query, we need to get to know plates count between candles within the query indices.

To save time, we need to precompute on s.
For a query [l, r], if we want to quickly find out the first candle after l, and the last candle before r. We can have two arrays to maintain the candle indexes.

When we have the candle indices, we also need a prefix sum of plates to calculate the plates between these two candles.

Ex: s = "* * | * * | * * * |" , queries : [[2,5],[5,9]]-> First we preprocess and calculate index of prevCandle, nextCandle, -> and count of '*' till current index in prefixSum vectorindex     :   0  1  2  3  4  5  6  7  8  9s       :  '*  *  |  *  *  |  *  *  *  |'prev      :  -1 -1  2  2  2  5  5  5  5  9next      :   2  2  2  5  5  5  9  9  9  9prefixSum :   1  2  2  3  4  4  5  6  7  70. query[0] = [2,5] => start = nextCandle[2] = 2=> end = prevCandle[5] =  5Thus, answer[0] = prefixSum[end] - prefixSum[start] = 4 - 2 = 21. query[1] = [5,9] => start = nextCandle[5] = 5=> end = prevCandle[9] =  9Thus, answer[1] = prefixSum[end] - prefixSum[start] = 7 - 4 = 3

And update plates count for each query.

Time Complexity: O(n). n = s.length().

Space: O(n).

AC Java:

class Solution {
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int n = s.length();
        int[] next = new int[n];
        int[] prev = new int[n];
        int[] prefix = new int[n];
        int canPrev = -1;
        int canNext = -1;
        int count = 0;
        for(int i = 0; i < n; i++){
            if(s.charAt(i) == '|'){
                canPrev = i; 
            }

            prev[i] = canPrev;

            if(s.charAt(n - 1 - i) == '|'){
                canNext = n - 1 - i;
            }

            next[n - 1 - i] = canNext;

            if(s.charAt(i) == '*'){
                count++;
            }

            prefix[i] = count;
        }

        int[] res = new int[queries.length];
        for(int i = 0; i < queries.length; i++){
            int left = queries[i][0];
            int right = queries[i][1];

            int start = next[left];
            int end = prev[right];
            if(start == -1 || end == -1){
                res[i] = 0;
            }else{
                int d = end - start;
                if(d <= 0){
                    res[i] = 0;
                }else{
                    res[i] = prefix[end] - prefix[start];
                }
            }
        }

        return res;
    }
}