1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
# 2055. Plates Between Candles
import bisect
"""
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 '*' represents a plate and '|' represents a candle. return an
integer array 'answer' where 'answer[i]' is the answer to the i'th query.
"""
class Solution(object):
def platesBetweenCandles(self, s, queries):
"""
:type s: str
:type queries: List[List[int]]
:rtype: List[int]
"""
dp = [i for i, j in enumerate(s) if j == "|"]
ans = []
for a, b in queries:
i = bisect.bisect_left(dp, a)
j = bisect.bisect(dp, b) - 1
ans.append((dp[j] - dp[i]) - (j - i) if i < j else 0)
return ans
if __name__ == "__main__":
obj = Solution()
print(obj.platesBetweenCandles(s="**|**|***|", queries=[[2, 5], [5, 9]]))
print(
obj.platesBetweenCandles(
s="***|**|*****|**||**|*",
queries=[[1, 17], [4, 5], [14, 17], [5, 11], [15, 16]],
)
)
|