Formatted question description: https://leetcode.ca/all/2055.html

# 2055. Plates Between Candles (Medium)

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] = [left`

denotes the _{i}, right_{i}]**substring** `s[left`

(_{i}...right_{i}]**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`

, 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* `i`

^{th}*query*.

**Example 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:**

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 <= 10`

^{5}`s`

consists of`'*'`

and`'|'`

characters.`1 <= queries.length <= 10`

^{5}`queries[i].length == 2`

`0 <= left`

_{i}<= right_{i}< s.length

**Companies**:

Amazon

**Related Topics**:

Array, String, Binary Search, Prefix Sum

**Similar Questions**:

- Find First and Last Position of Element in Sorted Array (Medium)
- Can Make Palindrome from Substring (Medium)

## Solution 1. Map + Binary Search

```
// OJ: https://leetcode.com/problems/plates-between-candles/
// Time: O((N + Q) * logN)
// Space: O(N)
class Solution {
public:
vector<int> platesBetweenCandles(string s, vector<vector<int>>& Q) {
map<int, int> m;
for (int i = 0, cnt = 0; i <= s.size(); ++i) {
if (i < s.size() && s[i] == '*') ++cnt;
else m[i] = cnt;
}
vector<int> ans;
for (auto &q : Q) {
auto a = m.lower_bound(q[0]);
auto b = prev(m.upper_bound(q[1]));
ans.push_back(max(0, b->second - a->second));
}
return ans;
}
};
```