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

'''
Input:
str s, queries: List[List[int]]

Output:
List[int] num_of_plates_for_each_query

Constraints:
- Q1: Can input be empty? A: Yes
- Q2: Is 0-indexed? A: Yes
- Q3: S consists of? A: "*"(plate), "|"(candle)
- Q4: Is query[i, j] inclusive? A: Yes
- Q5: Is len(queries[i]) == 2 and queries.left <= queries.right? A: Yes

Test Cases:
s = "**|**|***|", queries = [[2,5],[5,9]], return [2,3]
s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]], return [9,0,0,0,0]
 
[Solution 1: Binary Search Leftmost/Rightmost + Prefix Sum]
Idea:
# 1. computer prefix_sum[0...n] for # of plates in s
# 2. get candles idx as binary search input list
# 3. given query[i, j], do Binary Search to get leftmost "|"(candle) and rightmost "|"(candle)
# 4. get # of plates between leftmost "|"(candle) and rightmost "|"(candle), by prefix_sum[rightmost] - prefix_sum[leftmost + 1]
# --- check if no 2 candles in the given query range, then # of plates == 0

Time: O(s + len(queries) * logs)
Space: O(s + len(queries))

[TODO: Solution 2: Calculate leftmost_candle/rightmost_candle/candle_count for each s[i]]
# ref: https://leetcode.com/problems/plates-between-candles/discuss/1549018/JavaC%2B%2BPython-Binary-Search-and-O(Q-%2B-N)-Solution

Time: O(s + len(queries))
Space: O(s + len(queries))
'''


class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        result = []
        
        # 1. computer prefix_sum[0...n] for # of plates in s
        prefix_sum = self.get_prefix_sum(s)
        
        # 2. get candles idx as binary search input list
        candles_idx = [i for i, char in enumerate(s) if char == self.CANDLE]
        
        # 3. given query[start, end], do Binary Search to get leftmost "|"(candle) and rightmost "|"(candle)
        for query_start, query_end in queries:
            leftmost_candle_idx = self.binary_search_leftmost_candle(candles_idx, query_start, query_end)
            rightmost_candle_idx = self.binary_search_rightmost_candle(candles_idx, query_start, query_end)
        
            # 4. get # of plates between leftmost "|"(candle) and rightmost "|"(candle), by prefix_sum[rightmost] - prefix_sum[leftmost + 1]
            # --- check if no 2 candles in the given query range, then # of plates == 0
            num_of_plates_between_candles = None
            if leftmost_candle_idx == -1 or leftmost_candle_idx == rightmost_candle_idx:
                num_of_plates_between_candles = 0
            else:
                num_of_plates_between_candles = prefix_sum[rightmost_candle_idx] - prefix_sum[leftmost_candle_idx]
            result.append(num_of_plates_between_candles)
        
        return result


    '''
    helpers
    '''
    def __init__(self):
        self.CANDLE = "|"
        self.PLATE = "*"


    def get_prefix_sum(self, s: str) -> List[int]:
        n = len(s)
        
        prefix_sum = [0] * (n + 1)
        for i in range(1, n + 1):
            prefix_sum[i] = prefix_sum[i - 1] + (1 if s[i - 1] == self.PLATE else 0)
        
        return prefix_sum
    
    
    def binary_search_leftmost_candle(self, candles_idx: List[int], query_start: int, query_end: int) -> int:
        left = 0
        right = len(candles_idx) - 1
        while left <= right:
            mid = (left + right) // 2
            if candles_idx[mid] < query_start:
                left = mid + 1
            else:
                right = mid - 1
                
        if left > len(candles_idx) - 1 or candles_idx[left] > query_end:
            return -1
        
        return candles_idx[left]


    def binary_search_rightmost_candle(self, candles_idx: List[int], query_start: int, query_end: int) -> int:
        left = 0
        right = len(candles_idx) - 1
        while left <= right:
            mid = (left + right) // 2
            if candles_idx[mid] > query_end:
                right = mid - 1
            else:
                left = mid + 1
        
        if right < 0 or candles_idx[right] < query_start:
            return -1
        
        return candles_idx[right]
                
1884