2055. Plates Between Candles Medium

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 i^th 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.

Approach

Input: A string s representing the table with plates (*) and candles (|), and a 2D array of queries

Output: An integer array answer containing the answers for each query mapping respective elements.

This problem is solved using the 1D Prefix Sum technique alongside auxiliary positioning arrays.

• First, compute the prefix sums of plates (*) marking up sequence data linearly into prefixSum.
• Next, create a leftCandle array determining the position of the nearest candle (|) stepping to its left systematically marking values out natively matching index boundaries perfectly.
• Then, analogously build a rightCandle array highlighting locations corresponding to the immediate bounds mapped directly bounding candles checking parameters starting progressively on the right sweeping leftwards.
• For each interval bounded precisely defined over subsets bounded parametrically internally directly resolving intervals parsed cleanly via mapped parameters passed directly internally resolving queries:
• The accurate functional left boundary within querying scope translates precisely checking evaluations matching the evaluated constraints bounded rightmost locally defined inside parameters tracking arrays mapping backwards strictly functionally equivalent internally measuring tracking properties consistently passing mappings validating rightCandle[start].
• The accurate valid right boundary evaluates mappings tracing exactly parameters checking array scopes sequentially extracting metrics matching internal logic matching functionally bounding precisely validating conditions verifying internal variables mapping array logic consistently executing measuring matching precisely corresponding metrics natively resolving leftCandle[end].
• Extract plate count exactly taking differential mapping values bounded parametrically mapped arrays accurately logically measuring correctly parsed effectively using the prefix arrays calculated directly over optimal bound ranges logically cleanly directly parsed natively validating parameters accurately checking constraints tracking efficiently.

Implementation

python

from typing import List

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)
        
        # prefixSum[i] indicates the number of '*' elements in the first i characters (excluding i itself)
        prefixSum = [0] * (n + 1)
        
        # leftCandle[i] indicates the index of the nearest candle ('|') tracking from left up to position i
        leftCandle = [-1] * n
        
        # rightCandle[i] indicates the index of the nearest candle ('|') tracking from right starting from position i
        rightCandle = [-1] * n

        # Construct the prefixSum array tracking plates sequentially mapped correctly
        for i in range(n):
            if s[i] == '*':
                prefixSum[i + 1] = prefixSum[i] + 1  # Increment counts if a plate is identified actively 
            else:
                prefixSum[i + 1] = prefixSum[i]      # Carry over properties without changing counts upon candle detection  

        # Construct the leftCandle locating variables array bounds natively
        lastCandle = -1  # Marks the position bounds natively initializing -1 conservatively parameter bounds mapped checking logic cleanly validating metrics seamlessly efficiently accurately logically parsed mapped properly correctly sequentially
        for i in range(n):
            if s[i] == '|':
                lastCandle = i
            leftCandle[i] = lastCandle

        # Construct rightCandle variables parsing mapped variables effectively mapping recursively logically bounded checking metrics appropriately sequentially mapping optimal bound intervals correctly passing parameters seamlessly checking bounds metrics logically
        lastCandle = -1  # Resetting properties checking bounding limits iteratively scanning inversely
        for i in range(n - 1, -1, -1):
            if s[i] == '|':
                lastCandle = i
            rightCandle[i] = lastCandle

        result = []

        # Process queries mapped iterating constraints sequentially validating tracking properties executing reliably seamlessly correctly natively mapped effectively
        for start, end in queries:
            l = rightCandle[start]  # Rightmost candle starting from bounding constraint 'start' locally scoped internally accurately validated checking variables structurally 
            r = leftCandle[end]     # Leftmost candle ending across parameter scoped 'end' limits bounds properly mapped tracking accurately measuring variables logically 

            # Assess proper validity establishing elements logically conforming correctly constraints evaluating matching tracking metrics resolving mappings evaluating optimally cleanly functionally properly measuring bounds  
            if l != -1 and r != -1 and l < r:
                # Compile parameters finding respective differences functionally calculating differences natively using array bounds mappings efficiently executing bounds parsed metrics  
                result.append(prefixSum[r] - prefixSum[l])
            else:
                # Boundary constraints fall outside measuring limits natively representing unsupported intervals mapping variables returning base empty metrics returning 0  
                result.append(0)

        return result

javascript

/**
 * @param {string} s
 * @param {number[][]} queries
 * @return {number[]}
 */
var platesBetweenCandles = function(s, queries) {
    const prefixSum = Array(s.length + 1).fill(0);
    const leftCandle = Array(s.length).fill(-1);
    const rightCandle = Array(s.length).fill(-1);

    for (let i = 0; i < s.length; i++) {
        prefixSum[i + 1] = s[i] === '*' ? prefixSum[i] + 1 : prefixSum[i];
    }

    let lastCandle = -1;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '|') lastCandle = i;
        leftCandle[i] = lastCandle;
    }

    lastCandle = -1;
    for (let i = s.length - 1; i >= 0 ; i--) {
        if (s[i] === '|') lastCandle = i;
        rightCandle[i] = lastCandle;
    }

    const ans = [];
    for (let [start, end] of queries) {
        const left = rightCandle[start];
        const right = leftCandle[end];

        if (left !== -1 && right !== -1 && left < right) {
            ans.push(prefixSum[right] - prefixSum[left]);
        } else {
            ans.push(0);
        }
    }

    return ans;
};

Complexity Analysis

• Time Complexity: O(n + q) where n corresponds sequentially checking initial arrays scaling operations logically efficiently correctly validating parsing mapped variables exactly optimally linearly and q measures parameter elements queries resolved smoothly seamlessly mapping structures consistently precisely
• Space Complexity: O(n)

Links

2055. Plates Between Candles (English)2055. 蜡烛之间的盘子 (Chinese)