Plates Between Candles

Medium

LeetCode ↗

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 (at indices 6 and 7), 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:

ex-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:

ex-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

Explain Idea

Explanation

For each query [qleft, qright], we need the outermost pair of candles that still lies inside the query range. Counting directly inside every query would be too slow, so we first build candles, a sorted list of indices where s[i] == '|'.

Then each query becomes two binary searches on candles. The first search finds left_pos, the first candle index with candles[left_pos] >= qleft (left boundary candle). The second search finds right_pos, the last candle index with candles[right_pos] <= qright (right boundary candle). If either candle does not exist, or left_pos >= right_pos, the answer is 0.

If both boundaries exist, every character between candles[left_pos] and candles[right_pos] is either a plate or a candle. The distance between boundary indices is candles[right_pos] - candles[left_pos]. Inside that span, the number of candle-to-candle steps is right_pos - left_pos. The remaining positions are plates, so:

plates = (candles[right_pos] - candles[left_pos]) - (right_pos - left_pos)

Implementation

def platesBetweenCandles(s, queries):
  candles = []
  for i in range(len(s)):
      if s[i] == '|': candles.append(i)

  res = []
  for qleft, qright in queries:
      left_pos, right_pos = -1, -1

      # 1. find index of first candle that comes after qleft
      left, right = 0, len(candles)-1
      while left <= right:
          mid = (left+right) // 2
          if candles[mid] >= qleft:
              right = mid - 1
              left_pos = mid
          else:
              left = mid + 1

      # 2. find index of last candle that comes before qright
      left, right = 0, len(candles)-1
      while left <= right:
          mid = (left+right) // 2
          if candles[mid] <= qright:
              left = mid + 1
              right_pos = mid
          else:
              right = mid - 1

      # result = range between two outermost candles - candle count in between
      if (left_pos != -1) & (right_pos!= -1) & (right_pos > left_pos):
          res.append((candles[right_pos] - candles[left_pos]) - (right_pos - left_pos))
      else:
          res.append(0)
  return res

Intuition

Instead of counting the number of plates between two indices, which takes O(n) time, we can use the indices of the candles to figure out the number of plates between the candles (store in candles).

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator