LC-2055 Medium LeetCode

2055. Plates Between Candles

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 47% Topics: Array, String, Binary Search, Prefix Sum

Reading material

Arrays & Hashing 12 min Strings 12 min Binary Search 12 min

Reference solution (spoiler · python)

# Time:  O(n + q)
# Space: O(n)

class Solution(object):
    def platesBetweenCandles(self, s, queries):
        """
        :type s: str
        :type queries: List[List[int]]
        :rtype: List[int]
        """
        left, prefix = [0]*len(s), {}
        curr, cnt = -1, 0
        for i in xrange(len(s)):
            if s[i] == '|':
                curr = i
                cnt += 1
                prefix[i] = cnt
            left[i] = curr
        right = [0]*len(s)
        curr = len(s)
        for i in reversed(xrange(len(s))):
            if s[i] == '|':
                curr = i
            right[i] = curr
        return [max((left[r]-right[l]+1) - (prefix[left[r]]-prefix[right[l]]+1), 0) for l, r in queries]

Solution from kamyu104/LeetCode-Solutions · MIT