To solve this problem, we need to efficiently determine the number of plates ('*') between the nearest candles ('|') for each query range. The key insight is to preprocess the string to quickly find the nearest candles and compute the number of plates between them.

Approach

1. Precompute Nearest Candles:

   • Left Candle Array: For each position, store the index of the nearest candle to the left (including the position itself).
   • Right Candle Array: For each position, store the index of the nearest candle to the right (including the position itself).

2. Prefix Sum of Candles:

   • Compute a prefix sum array to quickly get the number of candles up to any position. This helps in calculating the number of candles between two positions.

3. Process Queries:

   • For each query, find the nearest candle to the right of the left query boundary and the nearest candle to the left of the right query boundary.
   • If these candles exist and are valid (left candle < right candle), calculate the number of plates between them using the precomputed arrays.

Solution Code

def platesBetweenCandles(s: str, queries: list[list[int]]) -> list[int]:
    n = len(s)
    left_candle = [-1] * n
    last = -1
    for i in range(n):
        if s[i] == '|':
            last = i
        left_candle[i] = last

    right_candle = [-1] * n
    last = -1
    for i in range(n-1, -1, -1):
        if s[i] == '|':
            last = i
        right_candle[i] = last

    prefix_candles = [0] * (n + 1)
    for i in range(n):
        prefix_candles[i+1] = prefix_candles[i] + (1 if s[i] == '|' else 0)

    res = []
    for l, r in queries:
        L = right_candle[l]
        R = left_candle[r]
        if L == -1 or R == -1 or L >= R:
            res.append(0)
        else:
            total_chars = R - L - 1
            num_candles = prefix_candles[R] - prefix_candles[L+1]
            res.append(total_chars - num_candles)
    return res

Explanation

1. Left Candle Array: This array helps find the nearest candle to the left of any position. For example, if the string is "||***|", the left candle at position 3 is 2 (since the nearest candle to the left is at index 2).

2. Right Candle Array: This array helps find the nearest candle to the right of any position. For example, the right candle at position 0 is 2 (since the nearest candle to the right is at index 2).

3. Prefix Sum Array: This array stores the cumulative count of candles up to each position. For example, the prefix sum at index 3 (for the string "||***|") is 1 (since there is one candle up to index 2).

4. Query Processing: For each query, we find the valid candles (L and R). The number of plates between them is calculated as the total characters between L and R minus the number of candles between them (using the prefix sum array).

This approach ensures that each query is processed in O(1) time after O(n) preprocessing, making it efficient for large inputs. The overall time complexity is O(n + q), where n is the length of the string and q is the number of queries. The space complexity is O(n) for storing the precomputed arrays.

作者声明:本文包含人工智能生成内容。