Question

Code

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        prefixSum = [0] * len(s)

        totalCandle = 0
        candles = []


        for i in range(len(s)):
            if s[i] == '|':
                totalCandle += 1
                candles.append(i)

            prefixSum[i] = totalCandle


        def findCandleBetween(left, right):

            # print(candles)

            leftMostCandle, rightMostCandle = -1, -1

            l, r = 0, len(candles) - 1

            while l <= r:
                m = l + (r - l) // 2

                if candles[m] < left:
                    l = m + 1
                else:
                    if m == 0 or candles[m - 1] < left:
                        leftMostCandle = candles[m]
                        break
                    else:
                        r = m - 1

            l, r = 0, len(candles) - 1

            while l <= r:
                m = l + (r - l) // 2

                if candles[m] > right:
                    r = m - 1
                else:
                    if m == len(candles) - 1 or candles[m + 1] > right:
                        rightMostCandle = candles[m]
                        break
                    else:
                        l = m + 1

            if rightMostCandle == -1 or leftMostCandle == -1:
                return 0 
        
            if rightMostCandle - leftMostCandle <= 0:
                return 0 


            return (rightMostCandle - leftMostCandle) - (prefixSum[rightMostCandle] - prefixSum[leftMostCandle])



        return [findCandleBetween(left, right) for left, right in queries]