<p>There is a long table with a line of plates and candles arranged on top of it. You are given a <strong>0-indexed</strong> string <code>s</code> consisting of characters <code>&#39;*&#39;</code> and <code>&#39;|&#39;</code> only, where a <code>&#39;*&#39;</code> represents a <strong>plate</strong> and a <code>&#39;|&#39;</code> represents a <strong>candle</strong>.</p>

<p>You are also given a <strong>0-indexed</strong> 2D integer array <code>queries</code> where <code>queries[i] = [left<sub>i</sub>, right<sub>i</sub>]</code> denotes the <strong>substring</strong> <code>s[left<sub>i</sub>...right<sub>i</sub>]</code> (<strong>inclusive</strong>). For each query, you need to find the <strong>number</strong> of plates <strong>between candles</strong> that are <strong>in the substring</strong>. A plate is considered <strong>between candles</strong> if there is at least one candle to its left <strong>and</strong> at least one candle to its right <strong>in the substring</strong>.</p>

<ul>
	<li>For example, <code>s = &quot;||**||**|*&quot;</code>, and a query <code>[3, 8]</code> denotes the substring <code>&quot;*||<strong><u>**</u></strong>|&quot;</code>. The number of plates between candles in this substring is <code>2</code>, as each of the two plates has at least one candle <strong>in the substring</strong> to its left <strong>and</strong> right.</li>
</ul>

<p>Return <em>an integer array</em> <code>answer</code> <em>where</em> <code>answer[i]</code> <em>is the answer to the</em> <code>i<sup>th</sup></code> <em>query</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="ex-1" src="https://assets.leetcode.com/uploads/2021/10/04/ex-1.png" style="width: 400px; height: 134px;" />
<pre>
<strong>Input:</strong> s = &quot;**|**|***|&quot;, queries = [[2,5],[5,9]]
<strong>Output:</strong> [2,3]
<strong>Explanation:</strong>
- queries[0] has two plates between candles.
- queries[1] has three plates between candles.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="ex-2" src="https://assets.leetcode.com/uploads/2021/10/04/ex-2.png" style="width: 600px; height: 193px;" />
<pre>
<strong>Input:</strong> s = &quot;***|**|*****|**||**|*&quot;, queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
<strong>Output:</strong> [9,0,0,0,0]
<strong>Explanation:</strong>
- queries[0] has nine plates between candles.
- The other queries have zero plates between candles.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> consists of <code>&#39;*&#39;</code> and <code>&#39;|&#39;</code> characters.</li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>queries[i].length == 2</code></li>
	<li><code>0 &lt;= left<sub>i</sub> &lt;= right<sub>i</sub> &lt; s.length</code></li>
</ul>

# Slightly modified Binary search
# Say you have an array [3, 5, 7, 9, 15] and you have an element
# 6 and you want to find closest elements on the left and right
# of 6 in the array. You can run binary search and ultimately
# r will point to 5 and l will point to 7, i.e r, l gives the boundary
# However, if the query is 5, both r, l will point to 5 (note)
# Also, if q is 16, r will point to 15 but l will point to an element
# at index = len(array) + 1 ( which doesn't exist) -- so need to handle
# these cases.

# Using this logic in this problem we'll use Binary Search to find 
# the closest candle on the right of the first element in the 
# query and the closest candle on the left of the second element in the query.
# The we'll use the prefix sum already computed to compute the 
# sum of the plates between these candles

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        look_up, pre_sum, res = [], [], []
        for i, e in enumerate(s):
            if s[i] == '|':
                look_up.append(i)
                pre_sum.append(pre_sum[-1] if pre_sum else 0)
            else:
                pre_sum.append(pre_sum[-1] + 1 if pre_sum else 1)
        
        for st, end in queries:
            _, r = self.range_bs(look_up, st)
            l, _ = self.range_bs(look_up, end)
            if st < end and 0<= r < len(look_up) and 0 <= l < len(look_up):
                res.append(
                    max(pre_sum[look_up[l]] - pre_sum[look_up[r]], 0)
                )
            else:
                res.append(0)
         
        return res
                
        
    def range_bs(self, look_up, q):
        l, r = 0, len(look_up) - 1
        while l <= r:
            mid = (l+r)//2
            if look_up[mid] == q:
                return mid, mid
            elif look_up[mid] < q:
                l = mid+1
            else:
                r = mid-1
        return r, l
1916