2055. Plates Between Candles - Detailed Explanation

Problem Statement

You are given a string s consisting of characters '*' (plates) and '|' (candles), and an array of queries where each query is a pair [left, right]. For each query, consider the substring s[left…right] (inclusive). You want to count the number of plates ('*') between the leftmost and rightmost candles ('|') within that substring. Return an array of answers, one per query.

Input

• s: a string of length n, made up of '*' and '|'
• queries: a list of q pairs [left, right], with 0 ≤ left ≤ right < n

Output

• A list of q integers, where the _i_th integer is the count of plates between candles in s[queries[i][0]…queries[i][1]]

Examples

Example 1

s = "**|**|***|"
queries = [[2,5],[5,9]]

• For [2,5], substring = "|**|". Plates between the two | are 2.
• For [5,9], substring = "|***|". Plates between are 3.
  Output: [2,3]

Example 2

s = "***|**|*****|**||**|*"
queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]

Output: [9,0,0,3,0]

Constraints

• 1 ≤ n, q ≤ 10⁵
• s[i] is either '*' or '|'
• 0 ≤ left ≤ right < n

Brute‑Force Approach

1. For each query [l,r], extract substring t = s[l…r].
2. Scan t to find the index of the first '|' (let’s call it a) and the last '|' (call it b).
3. If a < b, count the '*' in t[a+1…b−1]; otherwise answer is 0.
4. Repeat for all queries.

Time Complexity: O(q × n) in the worst case (each query may scan up to n characters)
Space Complexity: O(1) extra (ignoring output array)

Optimal Approach with Prefix Sums and Nearest‑Candle Pointers

To answer queries in O(1), preprocess the string once:

1. Prefix‑sum of plates

   • Let plates[i] = number of '*' in s[0…i−1].
   • Build in one pass:

     plates[0] = 0
     for i in [1…n]: plates[i] = plates[i−1] + (s[i−1]=='*'?1:0)
     

2. Nearest candle to the left

   • leftCandle[i] = index ≤ i of the closest '|'; or -1 if none.
   • Build by tracking last seen candle index.

3. Nearest candle to the right

   • rightCandle[i] = index ≥ i of the closest '|'; or n if none.
   • Build by scanning from right to left.

With these, for each query [l,r]:

• Let a = rightCandle[l], b = leftCandle[r].
• If a < b, plates between = plates[b] − plates[a]; otherwise 0.

Building Helpers in One Pass Each

plates = int[n+1]
leftCandle = int[n]
rightCandle = int[n]

# prefix plates
plates[0] = 0
for i in 1…n:
  plates[i] = plates[i-1] + (s[i-1]=='*'?1:0)

# leftCandle
last = -1
for i in 0…n-1:
  if s[i]=='|': last = i
  leftCandle[i] = last

# rightCandle
next = n
for i in n-1…0:
  if s[i]=='|': next = i
  rightCandle[i] = next

Query in O(1)

for each [l,r]:
  a = rightCandle[l]
  b = leftCandle[r]
  if a < b:
    answer = plates[b] - plates[a]
  else
    answer = 0

Overall Time Complexity: O(n + q)
Space Complexity: O(n)

Python Code