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

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        # # Method #1:
        # # res = []
        # # for start, end in queries:
        # #     total = 0
        # #     left, right = None, None
        # #     ctr = 0
        # #     for i in range(start, end + 1):
        # #         if s[i] == '|' and not left:
        # #             left = True

        # #         elif i > start and s[i] == '|' and s[i - 1] == '|':
        # #             continue

        # #         elif left and s[i] == '*':
        # #             ctr += 1

        # #         elif left and not right and ctr > 0:
        # #             right = True
        # #             total += ctr
        # #             ctr = 0
        # #             right = None

        # #     res.append(total)
        # # return res
        # # Method #2:
        # n = len(s)
        
        # # Step 1: Precompute left_candle and right_candle
        # left_candle = [-1] * n
        # right_candle = [-1] * n
        
        # # Fill left_candle array
        # candle_index = -1
        # for i in range(n):
        #     if s[i] == '|':
        #         candle_index = i
        #     left_candle[i] = candle_index
        
        # # Fill right_candle array
        # candle_index = -1
        # for i in range(n - 1, -1, -1):
        #     if s[i] == '|':
        #         candle_index = i
        #     right_candle[i] = candle_index
        
        # # Step 2: Precompute plates_prefix
        # plates_prefix = [0] * n
        # plates_count = 0
        # for i in range(n):
        #     if s[i] == '*':
        #         plates_count += 1
        #     plates_prefix[i] = plates_count
        
        # # Step 3: Answer each query
        # result = []
        # for left, right in queries:
        #     # Find the nearest candles within the range
        #     left_bound = right_candle[left]
        #     right_bound = left_candle[right]
            
        #     # If the bounds are valid and form a valid range
        #     if left_bound != -1 and right_bound != -1 and left_bound < right_bound:
        #         result.append(plates_prefix[right_bound] - plates_prefix[left_bound])
        #     else:
        #         result.append(0)
        
        # return result
        # # Method #3:
        # sums = []
        # p = "*"
        # c = "|"
        # for q in queries:
        #     se = s[q[0]:q[1]+1]
        #     first_index = se.find(c) 
        #     last_index = se.rfind(c)
        #     new = se[first_index:last_index]
        #     sums.append(new.count(p))
        # return sums

        candies = [i for i, c in enumerate(s) if c == "|"]
        
        def bns(x: int) -> int:
            l, r = 0, len(candies) - 1
            while l <= r:
                m = (l + r) // 2
                if candies[m] < x: l = m + 1
                else: r = m - 1
            return l

        ans = []
        for a, b in queries:
            l, r = bns(a), bns(b + 1) - 1
            ans.append(candies[r] - candies[l] - (r - l) if l < r else 0)
        return ans
















1785