We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Plates Between Candles

Difficulty: Medium

Problem Description

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_i, right_i] denotes the 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.

Key Insights

  • The task is to count plates '*' that are strictly between candles '|' in specified substrings.
  • A plate is counted only if it has candles on both sides within the specified substring.
  • Efficient handling of multiple queries (up to 100,000) is crucial given the string length can also be up to 100,000.
  • Utilizing prefix sums can help in precomputing the number of plates and the positions of candles, allowing for quick query responses.

Space and Time Complexity

Time Complexity: O(n + q) where n is the length of the string and q is the number of queries.
Space Complexity: O(n) for storing prefix sums and candle positions.

Solution

To solve this problem, we can employ the following approach:

  1. Create a prefix sum array to count the number of plates '*' encountered up to each index.
  2. Maintain an array to store the positions of candles '|' to quickly find the nearest candles for any query.
  3. For each query, identify the left and right boundaries of the substring, locate the nearest candles, and use the prefix sums to count the plates between these candles.

Code Solutions

def platesBetweenCandles(s, queries):
    n = len(s)
    prefix = [0] * n
    candle_positions = []
    
    # Build prefix sum and candle positions
    for i in range(n):
        if s[i] == '*':
            prefix[i] = (prefix[i - 1] + 1) if i > 0 else 1
        else:
            prefix[i] = prefix[i - 1] if i > 0 else 0
            candle_positions.append(i)
    
    result = []
    
    for left, right in queries:
        # Find the first candle on the right and last candle on the left
        left_candle = -1
        right_candle = -1
        
        # Binary search for the right candle
        for pos in candle_positions:
            if pos > right:
                break
            right_candle = pos
        
        # Binary search for the left candle
        for pos in reversed(candle_positions):
            if pos < left:
                break
            left_candle = pos
        
        if left_candle != -1 and right_candle != -1 and left_candle < right_candle:
            plates_count = prefix[right_candle] - (prefix[left_candle] if left_candle > 0 else 0)
            result.append(plates_count)
        else:
            result.append(0)
    
    return result
← Back to All Questions